Setup notebook

The following libraries are used for this notebook:

# Load libraries
library(tidyverse)
library(tidymodels)
library(glmnet)
library(leaps)
library(naniar)
library(skimr)
library(knitr)
library(corrplot)
library(ranger)
library(doParallel)
library(themis)
library(vip)

Load data listings

# Read csv with listing information
data <- read_csv(gzfile("listings.csv.gz"))

Part 1: Data Cleaning and Feature Selection

Select variables of interest

The goal of the assignment is to build a model that predicts the prices of listings on AirBnB in Amsterdam. The outcomes of the model will be used for suggestions to the new hosts about the average platform price for similar listings. Afterwards, hosts can choose whether they want to use the recommendation to set their prices accordingly in order to be competitive and gain attention from the guests since the beginning. All variables including information on the reviews provide information about a listing after it has been published. Therefore, these variables are not included in the data set. Moreover, the variables including a description and summary about the listing can be analyzed using NLP (e.g. sentiment analysis). However, this is beyond the scope of the assignment. Therefore, these variables are excluded from the model. The variables below are included in the data set for further analysis and cleaning.

# Generate subset with variables of interest
data_sub <- data %>%
  select(id, price, property_type, room_type, accommodates, bathrooms, bedrooms,
         beds, bed_type, amenities, host_since, host_response_time,
         host_response_rate, host_neighbourhood, host_listings_count, 
         host_verifications, host_identity_verified, neighbourhood_cleansed,
         square_feet, cleaning_fee, guests_included, extra_people, 
         minimum_nights, maximum_nights, availability_30, availability_60,
         availability_90, availability_365, instant_bookable, 
         cancellation_policy, require_guest_profile_picture,
         require_guest_phone_verification, calculated_host_listings_count,
         calculated_host_listings_count_entire_homes, 
         calculated_host_listings_count_private_rooms,
         calculated_host_listings_count_shared_rooms)
# Inspect data
head(data_sub)
# Inspect data
skim(data_sub) %>% knit_print()
Data summary
Name data_sub
Number of rows 20025
Number of columns 36
_______________________
Column type frequency:
character 13
Date 1
logical 4
numeric 18
________________________
Group variables None

Variable type: character

skim_variable n_missing complete_rate min max empty n_unique whitespace
price 0 1.00 5 9 0 479 0
property_type 0 1.00 3 22 0 34 0
room_type 0 1.00 10 15 0 4 0
bed_type 0 1.00 5 13 0 5 0
amenities 0 1.00 2 1303 0 19213 0
host_response_time 158 0.99 3 18 0 5 0
host_response_rate 158 0.99 2 4 0 61 0
host_neighbourhood 5972 0.70 4 35 0 81 0
host_verifications 0 1.00 2 158 0 381 0
neighbourhood_cleansed 0 1.00 4 38 0 22 0
cleaning_fee 3604 0.82 5 7 0 112 0
extra_people 0 1.00 5 7 0 112 0
cancellation_policy 0 1.00 8 27 0 5 0

Variable type: Date

skim_variable n_missing complete_rate min max median n_unique
host_since 158 0.99 2008-09-24 2019-12-06 2015-02-08 3133

Variable type: logical

skim_variable n_missing complete_rate mean count
host_identity_verified 158 0.99 0.39 FAL: 12094, TRU: 7773
instant_bookable 0 1.00 0.26 FAL: 14839, TRU: 5186
require_guest_profile_picture 0 1.00 0.01 FAL: 19819, TRU: 206
require_guest_phone_verification 0 1.00 0.01 FAL: 19758, TRU: 267

Variable type: numeric

skim_variable n_missing complete_rate mean sd p0 p25 p50 p75 p100 hist
id 0 1.00 19117026.00 11473019.80 2818 9631819 18418621 27913527.0 40655209 ▇▇▇▅▆
accommodates 0 1.00 2.87 1.30 1 2 2 4.0 18 ▇▁▁▁▁
bathrooms 6 1.00 1.18 0.39 0 1 1 1.5 8 ▇▁▁▁▁
bedrooms 13 1.00 1.45 0.89 0 1 1 2.0 12 ▇▁▁▁▁
beds 31 1.00 1.79 1.41 0 1 1 2.0 32 ▇▁▁▁▁
host_listings_count 158 0.99 3.85 28.93 0 1 1 1.0 751 ▇▁▁▁▁
square_feet 19662 0.02 542.88 560.24 0 0 484 834.0 3229 ▇▅▁▁▁
guests_included 0 1.00 1.46 0.95 1 1 1 2.0 16 ▇▁▁▁▁
minimum_nights 0 1.00 3.43 14.74 1 2 2 3.0 1001 ▇▁▁▁▁
maximum_nights 0 1.00 613.89 548.62 1 20 1125 1125.0 11250 ▇▁▁▁▁
availability_30 0 1.00 4.46 7.81 0 0 0 6.0 30 ▇▁▁▁▁
availability_60 0 1.00 10.05 17.14 0 0 0 13.0 60 ▇▁▁▁▁
availability_90 0 1.00 15.69 26.77 0 0 0 19.0 90 ▇▁▁▁▁
availability_365 0 1.00 47.93 95.34 0 0 0 37.0 365 ▇▁▁▁▁
calculated_host_listings_count 0 1.00 1.97 5.20 1 1 1 1.0 72 ▇▁▁▁▁
calculated_host_listings_count_entire_homes 0 1.00 1.50 5.06 0 1 1 1.0 72 ▇▁▁▁▁
calculated_host_listings_count_private_rooms 0 1.00 0.38 1.08 0 0 0 0.0 16 ▇▁▁▁▁
calculated_host_listings_count_shared_rooms 0 1.00 0.01 0.09 0 0 0 0.0 3 ▇▁▁▁▁

Data cleaning

Basic cleaning

First, we converted all categorical and logical variables, which did not need any further cleaning, to data type factor.

# Convert categorical vars to factors 
data_sub$property_type <- factor(data_sub$property_type , 
                                 levels = unique(data_sub$property_type))
data_sub$room_type <- factor(data_sub$room_type , 
                             levels = unique(data_sub$room_type))
data_sub$bed_type <- factor(data_sub$bed_type , 
                    levels = unique(data_sub$bed_type))
data_sub$host_response_time <- factor(data_sub$ host_response_time, 
                    levels = unique(data_sub$host_response_time))
data_sub$host_neighbourhood <- factor(data_sub$host_neighbourhood, 
                    levels = unique(data_sub$host_neighbourhood))
data_sub$neighbourhood_cleansed <- factor(data_sub$neighbourhood_cleansed, 
                    levels = unique(data_sub$neighbourhood_cleansed))
data_sub$cancellation_policy <- factor(data_sub$cancellation_policy , 
                    levels = unique(data_sub$cancellation_policy))

# Convert logical variables to factors
data_sub$host_identity_verified <- factor(data_sub$host_identity_verified)
data_sub$instant_bookable <- factor(data_sub$instant_bookable)
data_sub$require_guest_profile_picture <- 
  factor(data_sub$require_guest_profile_picture)
data_sub$require_guest_phone_verification <- 
  factor(data_sub$require_guest_phone_verification)

Second, some of the variables contain numeric variables, however, they are stored in a string containing a dollar or percentage sign. The signs were removed from the strings, and the remaining numbers were converted to numeric variables.

# Remove $ sign from columns containing prices and convert to doubles
data_sub$price <- as.double(gsub("[,$]", "", data_sub$price))
data_sub$cleaning_fee <- as.double(gsub("[,$]", "", data_sub$cleaning_fee))
data_sub$extra_people <- as.double(gsub("[,$]", "", data_sub$extra_people))

# Replace "N/A" values, remove % and convert to percentage 
data_sub$host_response_rate <- na_if(data_sub$host_response_rate, "N/A")
data_sub$host_response_rate <- 
  as.double(gsub("[%]", "", data_sub$host_response_rate)) / 100

Clean amenities

The variable amenities contains all the amenities of the listing. However, this was stored in one large string, and the elements could not be accessed separately. Therefore, we cleaned the string and splitted it to a list containing the separated elements. Furthermore, we extracted all unique amenities and stored these in a vector.

# Clean and split strings for amenities
# Returns a list with all unique values
clean_amenities <- function(x) {
  subbed <- gsub('[{}\"]', "", tolower(x))
  splitted <- str_split(subbed, ",")
  clean <- sapply(splitted, function(x) str_trim(x, side = "both"))
  return(clean)
}

# Clean amenities
data_sub$amenities_clean <- 
  sapply(data_sub$amenities, function(x) clean_amenities(x))

# Create vector with all unique amenities
amenities_unique = c()
for(amenities in data_sub$amenities_clean) {
  for(element in amenities) {
    if(!(element %in% amenities_unique) & element != "") {
      amenities_unique <- append(amenities_unique, str_trim(element))
    }
  }
}
amenities_unique
  [1] "internet"                                   "wifi"                                       "paid parking off premises"                  "buzzer/wireless intercom"                  
  [5] "heating"                                    "washer"                                     "smoke detector"                             "carbon monoxide detector"                  
  [9] "first aid kit"                              "safety card"                                "fire extinguisher"                          "essentials"                                
 [13] "shampoo"                                    "lock on bedroom door"                       "24-hour check-in"                           "hangers"                                   
 [17] "hair dryer"                                 "iron"                                       "laptop friendly workspace"                  "translation missing: en.hosting_amenity_49"
 [21] "translation missing: en.hosting_amenity_50" "private entrance"                           "hot water"                                  "bed linens"                                
 [25] "extra pillows and blankets"                 "single level home"                          "garden or backyard"                         "no stairs or steps to enter"               
 [29] "accessible-height bed"                      "host greets you"                            "handheld shower head"                       "paid parking on premises"                  
 [33] "tv"                                         "refrigerator"                               "long term stays allowed"                    "cable tv"                                  
 [37] "kitchen"                                    "elevator"                                   "indoor fireplace"                           "family/kid friendly"                       
 [41] "dryer"                                      "private living room"                        "well-lit path to entrance"                  "breakfast"                                 
 [45] "self check-in"                              "smart lock"                                 "lake access"                                "pets live on this property"                
 [49] "cat(s)"                                     "smoking allowed"                            "pets allowed"                               "microwave"                                 
 [53] "coffee maker"                               "dishwasher"                                 "dishes and silverware"                      "cooking basics"                            
 [57] "oven"                                       "stove"                                      "patio or balcony"                           "keypad"                                    
 [61] "luggage dropoff allowed"                    "baby bath"                                  "bathtub"                                    "babysitter recommendations"                
 [65] "beach essentials"                           "cleaning before checkout"                   "ev charger"                                 "pack ’n play/travel crib"                  
 [69] "high chair"                                 "crib"                                       "children’s books and toys"                  "room-darkening shades"                     
 [73] "children’s dinnerware"                      "free street parking"                        "other"                                      "extra space around bed"                    
 [77] "wheelchair accessible"                      "pocket wifi"                                "wide hallways"                              "waterfront"                                
 [81] "washer / dryer"                             "window guards"                              "air conditioning"                           "suitable for events"                       
 [85] "free parking on premises"                   "lockbox"                                    "wide entrance for guests"                   "bbq grill"                                 
 [89] "ground floor access"                        "dog(s)"                                     "hot tub"                                    "wide entrance"                             
 [93] "accessible-height toilet"                   "wide entryway"                              "hot water kettle"                           "ethernet connection"                       
 [97] "flat path to guest entrance"                "wide doorway to guest bathroom"             "wide clearance to shower"                   "toilet"                                    
[101] "step-free shower"                           "gym"                                        "outlet covers"                              "firm mattress"                             
[105] "changing table"                             "stair gates"                                "fireplace guards"                           "table corner guards"                       
[109] "game console"                               "baby monitor"                               "doorman"                                    "building staff"                            
[113] "pool"                                       "other pet(s)"                               "fixed grab bars for shower"                 "disabled parking spot"                     
[117] "electric profiling bed"                     "bathtub with bath chair"                    "shower gel"                                 "fixed grab bars for toilet"                
[121] "beachfront"                                 "shower chair"                               "trash can"                                  "ski-in/ski-out"                            
[125] "mobile hoist"                               "pool with pool hoist"                       "ceiling hoist"                              "full kitchen"                              
[129] "private bathroom"                           "air purifier"                               "bread maker"                                "roll-in shower with chair"                 

Create new variables based information stored in amenities

Separate variables could be created from the vector containing all unique amenities. However, since there are 130 usable amenities it seemed beyond the scope of the assignment. Moreover, some of the amenities contain information that is also given by other variables or about other amenities. For example a private bathroom could also be a strong indicator that the listing is an entire house/apartment. Also, shampoo or shower gel could be strong indicators for the presence of a bathroom. Furthermore, some amenities are very specific and apply only to a few or one house. Yet, variables are created for some of the amenities that could have an influence on the price of a listing. We created variables for wifi, pool, hot_tub and tv.

# Create variable for WIFI and add to data set
wifi <- vector()
for(i in 1:length(data_sub$amenities_clean)) {
  if("wifi" %in% data_sub$amenities_clean[[i]] | 
     "internet" %in% data_sub$amenities_clean[[i]]) {
    wifi[i] <-  "yes"
  } else {
    wifi[i] <-  "no"
  }
}
data_sub$wifi <- wifi
data_sub$wifi <- factor(data_sub$wifi, levels = c("yes", "no"))

# Create variable for pool and add to data set
pool <- vector()
for(i in 1:length(data_sub$amenities_clean)) {
  if("pool" %in% data_sub$amenities_clean[[i]] |
     "pool with pool hoist" %in% data_sub$amenities_clean[[i]]) {
    pool[i] <-  "yes"
  } else {
    pool[i] <-  "no"
  }
}
data_sub$pool <- pool
data_sub$pool <- factor(data_sub$pool, levels = c("yes", "no"))

# Create variable for hot_tub and add to data set
hot_tub <- vector()
for(i in 1:length(data_sub$amenities_clean)) {
  if("hot tub" %in% data_sub$amenities_clean[[i]]) {
    hot_tub[i] <-  "yes"
  } else {
    hot_tub[i] <-  "no"
  }
}
data_sub$hot_tub <- hot_tub
data_sub$hot_tub <- factor(data_sub$hot_tub, levels = c("yes", "no"))

# Create variable for hot_tub and add to data set
tv <- vector()
for(i in 1:length(data_sub$amenities_clean)) {
  if("tv" %in% data_sub$amenities_clean[[i]] |
     "cable tv" %in% data_sub$amenities_clean[[i]]) {
    tv[i] <-  "yes"
  } else {
    tv[i] <-  "no"
  }
}
data_sub$tv <- tv
data_sub$tv <- factor(data_sub$tv, levels = c("yes", "no"))

Clean host verification methods

The same reasoning from the amenities section above applies to the variable host_verification. The same cleaning method was used as for amenities, first we cleaned and splitted the strings, thereafter a vector with all unique host verification methods is generated.

# Clean and split strings for host verification methods
# Returns a list with all unique values
clean_verficiations <- function(x) {
  subbed <- gsub("\\[|\\]", "", tolower(x))
  subbed_complete <- gsub("[']", "", subbed)
  splitted <- str_split(subbed_complete, ",")
  clean <- sapply(splitted, function(x) str_trim(x, side = "both"))
  return(clean)
}

# Clean host_verifications
data_sub$host_verifications_clean <- 
  sapply(data_sub$host_verifications, function(x) clean_verficiations(x))

# Generate list with all unique host verification methods
verifications_unique = c()
for(verifications in data_sub$host_verifications_clean) {
  for(element in verifications) {
    if(!(element %in% verifications_unique) & element != "") {
      verifications_unique <- append(verifications_unique, str_trim(element))
    }
  }
}
verifications_unique
 [1] "email"                 "phone"                 "reviews"               "jumio"                 "offline_government_id" "selfie"                "government_id"        
 [8] "identity_manual"       "facebook"              "work_email"            "none"                  "google"                "manual_offline"        "manual_online"        
[15] "sent_id"               "kba"                   "weibo"                 "zhima_selfie"          "sesame"                "sesame_offline"       

Create variables based on information stored in host verifications

Separate variables are created for the most common methods of verification, namely email, phone, facebook and government_id.

# Create variable for host email and add to data set
host_email <- vector()
for(i in 1:length(data_sub$host_verifications_clean)) {
  if("email" %in% data_sub$host_verifications_clean[[i]]) {
    host_email[i] <-  "yes"
  } else {
    host_email[i] <-  "no"
  }
}
data_sub$host_email <- host_email 
data_sub$host_email <- factor(data_sub$host_email, levels = c("yes", "no"))

# Create variable for phone and add to data set 
host_phone <- vector()
for(i in 1:length(data_sub$host_verifications_clean)) {
  if("phone" %in% data_sub$host_verifications_clean[[i]]) {
    host_phone[i] <-  "yes"
  } else {
    host_phone[i] <-  "no"
  }
}
data_sub$host_phone <- host_phone 
data_sub$host_phone <- factor(data_sub$host_phone, levels = c("yes", "no"))
 
# Create variable for host facebook and add to data set
host_facebook <- vector()
for(i in 1:length(data_sub$host_verifications_clean)) {
  if("facebook" %in% data_sub$host_verifications_clean[[i]]) {
    host_facebook[i] <-  "yes"
  } else {
    host_facebook[i] <-  "no"
  }
}
data_sub$host_facebook <- host_facebook 
data_sub$host_facebook <- 
  factor(data_sub$host_facebook, levels = c("yes", "no"))

# Create variable for government id 
host_government_id <- vector()
for(i in 1:length(data_sub$host_verifications_clean)) {
  if("government_id" %in% data_sub$host_verifications_clean[[i]]) {
    host_government_id[i] <-  "yes"
  } else {
    host_government_id[i] <-  "no"
  }
}
data_sub$host_government_id <- host_government_id 
data_sub$host_government_id <- 
  factor(data_sub$host_government_id, levels = c("yes", "no"))

Clean date variables

We used the variable host_since to create a new variable host_years_active, which contains information regarding the number of years a host has been active on the platform.

# Create new variable for active years host 
data_sub <- data_sub %>% 
  mutate(host_years_active = 
           as.double(as.Date("2019-12-07") - host_since) / 365)

Inspect availability variables

The variables availability_30, availability_60, availability_90 and availability_365 carry some of the same information. In order to inspect if all variables should be included in the data set, we plotted a correlation matrix. The plot below shows that all variables indicating the availability are strongly correlated. Therefore, only the variable availability_30 is included for further analysis.

# Plot correlation matrix
data_sub %>% select_if(is.numeric) %>% 
  select(availability_30, availability_60, availability_90, availability_365) %>% 
  cor() %>% corrplot()


# Remove other availability variables from data set
data_sub <- 
  data_sub %>% 
  select(-availability_60, -availability_90, -availability_365) 

Check missing data

In order to inspect which variables have missing cases, and how many there are in general, a table is constructed. The table shows the variables in the data set which contain missing values (in descending order). The table shows that the variable square_feet has \(19662\) missing cases, which is about \(98.19\%\). If we would deleted the missing cases, the data set will barely contain any data. Moreover, other methods for handling missing values, like replacing NA-values with the mean or median, would not be appropriate as the variables will be based on only \(1.81\%\) of the data. Therefore, square_feet is not included in the final. The variable host_response_rate has \(9349\) missing cases, which is about \(46.69\%\). The variable host_neighbourhood has \(5972\), which is about \(29.82\%\). The variable cleaning_fee has \(3604\), which is about \(18.00\%\). The variables host_response_rate, host_neighbourhood and cleaning_fee do not have as many missing values as square_feet, however, the same reasoning applies. Due to these findings, these variables are also excluded from the analyses.

# Count missing cases per variable
na_counter <- sapply(data_sub, function(x) sum(is.na(x)))
vars <- colnames(data_sub)

# Extract all variables with NA-values
na_values <- tibble(variables = vars, na_count = na_counter) 

# Check na count per variable
na_values %>%
  filter(na_count > 0) %>%
  arrange(desc(na_count))

Moreover, a check is performed on the number of cases that contain missing values if the other values that have missing cases would be included in the ‘final’ data set. The table below shows that there are 206 cases which contain missing values, which is about \(1.03\%\) of the entire data set. Since this is a very small proportion it is not very likely that deleting these cases would have a large impact on the predictions. Furthermore, all models that will be performed cannot handle missing values. Therefore, the cases with missing values are deleted.

# Compute incomplete rows
data_sub %>% 
  select(host_since, host_response_time, host_listings_count,
         host_identity_verified, beds, bedrooms, host_years_active, 
         bathrooms) %>% 
  complete.cases() %>% 
  summary(count())
   Mode   FALSE    TRUE 
logical     206   19819 
# Select variables for data set
variables_analysis <-   
  na_values %>% 
  filter(na_count <= 158) %>% 
  select(variables) %>% 
  pull(variables)

# Create final data set
data_semi_final <- data_sub %>% select(all_of(variables_analysis))
data_semi_final <- data_semi_final %>% 
  select(-c(amenities, amenities_clean, host_verifications,
            host_verifications_clean, host_since))
data_final <- data_semi_final[complete.cases(data_semi_final), ]

Create train-test split

For further analysis the data is split into a train-test set.

# Create a train-split sets
seed_x <-  123
set.seed(seed_x)
data_split <- initial_split(data_final, prop = 0.7)
data_train <- training(data_split)
data_test <- testing(data_split)

Inspecting the predicted variable

In order to prevent data leakages we only inspect the predicted variable price in the training set. In order to inspect price we have created a distribution plot. The plot shows that the data set contains some outliers and that the distribution is rightly skewed. Both the outliers and the skeweness make the data less interpretable and this could have an influence on performance of the models.

# Plot distribution price
ggplot(data = data_train , aes(price)) +
  geom_histogram(col="black",
                 breaks=seq(0, max(data_train$price), by=75),
                 aes(fill=..count..)) +
  labs(title="Distribution for Price", x="Price", y="Count") +
  scale_fill_gradient("Count", low="green", high="red") +
  theme(plot.title = element_text(hjust = 0.5))

In order to prevent these potential problems we created a new distribution plot with a log transformed variable price. The plot shows that the distribution is less skewed and does not contain many large outliers. Consequently, the data is more interpretable. Therefore, we will use the log transformed price for our models.

# Plot distribution price
ggplot(data = data_train , aes(log(price + 1))) +
  geom_histogram(col="black",
                 aes(fill=..count..)) +
  labs(title="Distribution for Ln Price", x="Ln Price", y="Count") +
  scale_fill_gradient("Count", low="green", high="red") +
  theme(plot.title = element_text(hjust = 0.5))

# Log transform the price in for both training and test set
data_final$price <- log(data_final$price + 1)

# Resplit the data using the same seed 
set.seed(seed_x)
data_split <- initial_split(data_final, prop = 0.7)
data_train <- training(data_split)
data_test <- testing(data_split)

K-fold cross validation

Moreover, we have generated 10-fold cross validation sets.

# Generate 10-fold CV sets
set.seed(321)
data_folds <- vfold_cv(data_train, v = 10)
data_folds
#  10-fold cross-validation 

Remove data frames to avoid leakages and errors

rm(data)
rm(data_sub)
rm(data_semi_final)
rm(na_values)

Part 2: Modelling Approaches

Linear Lasso Regularized Regression Model

In this section, a regularized regression model will be specified and trained. A lasso penalty is chosen to simultaneously perform subset selection. Therefore, a mixture is set to 1 in the model specification.

Model specification

Specification of lasso-regularized logistic regression model, where the penalty parameter will be tuned:

# Specify the model and engine used
lasso_linreg <- linear_reg(penalty = tune(), mixture = 1) %>% 
  set_engine("glmnet")

# Check that model specified correctly:
lasso_linreg %>% translate()

Preprocessing recipe

In this section, the recipe is formulated. All the final dataset variables are included in the recipe, in order to perform the subset selection by means of a lasso penalty. As the property type and bed type have some categories with just a few observations, the categories that include less than 1% of the total number of observations are combined to “other” category to avoid sparse data. Additionally, dummies are created for all of the nominal variables. Lastly, all the variables are normalized.

# Prepare the recipe by setting up the regression model, setting id as id variable, combining small categories to other class, and creating dummies and normalizing variables
lasso_recipe <-  recipe(price ~ ., 
                          data = data_train) %>% 
                        update_role(id, new_role = "ID") %>%
                        step_other(property_type, bed_type,  threshold = 0.01, other = "other values") %>% 
                        step_dummy(all_nominal(), -all_outcomes()) %>%
                        step_normalize(all_predictors(), -all_outcomes())
lasso_recipe

Testing that this works properly:

# Prepare and bake the data (on training set) to check that the recipe prepares the data correctly
data_baked <- lasso_recipe %>% prep(data_train) %>% bake(data_train)
head(data_baked)

Create Lasso Workflow

# Combine the model specification and reciple to a workflow
lasso_wf <- workflow() %>% 
  add_recipe(lasso_recipe) %>% 
  add_model(lasso_linreg)
lasso_wf

Tuning grids

Next, the \(\lambda\) parameter of the lasso model will be tuned. For that purpose, a tuning grid is specified.

# Set tuning grid
grid_lasso <- tibble(penalty = 10^(seq(from = -5, to = 1, length.out = 70)))

Tuning lasso-penalized linear regression

10-k-cross-validation is used to tune the lasso-penalized linear regression, and the metrics are plotted against the different values of \(\lambda\).

 # Perform grid search over the tuning grid of penalty values
 lasso_tune <- lasso_wf %>% 
  tune_grid(resamples = data_folds, 
            grid = grid_lasso,
            metrics = metric_set(mae, rmse, rsq_trad))
# Store metrics in variable
lasso_tune_metrics <- lasso_tune %>% 
  collect_metrics()

# Plot all results metrics 
lasso_tune_metrics %>%
  ggplot(aes(x = penalty, y = mean, 
             ymin = mean - std_err, ymax = mean + std_err)) + 
  geom_linerange(alpha = 0.5, colour = "red") + 
  geom_point(colour = "red") + 
   facet_wrap(~ .metric, scale = "free_y") +
  scale_x_log10() + 
  labs(y = "Lasso Performance Metrics", x = expression(lambda))


# Plot MAE 
lasso_tune_metrics %>% filter(.metric == "mae") %>% 
  ggplot(aes(x = penalty, y = mean, 
             ymin = mean - std_err, ymax = mean + std_err)) + 
  geom_linerange(alpha = 0.5, colour = "red") + 
  geom_point(colour = "red") + 
  scale_x_log10() + 
  labs(y = "mae", x = expression(lambda), 
       title = "Lasso Regresssion MAE")

Next, the Lambda value which results in best model performance on the train set is selected. It can be seen that as the RMSE is more sensitive for large residuals, the standard errors of these metrics are larger compared to the standard errors of mean absolute error (MAE). Therefore, the mean absolute error is used to select the best model.

# Show best models with corresponding penalty values
lasso_tune %>% show_best("mae")

The best model is selected using the one standard error rule, where the simplest model that has MAE inside one standard error from the absolute best model is chosen to avoid overfitting.

# Select best model according to 1 std error rule
lasso_1se_model <- select_by_one_std_err(lasso_tune, metric = "mae", desc(penalty))
lasso_1se_model

As can be seen, the best model has a penalty parameter of 0.007.

Finalize the workflow:

# Finalize lasso wf with the selected best model
lasso_wf_tuned <- 
  lasso_wf %>% 
  finalize_workflow(lasso_1se_model)
lasso_wf_tuned
# Train the tuned model on all of the train data and test on the test data 
lasso_last_fit <- lasso_wf_tuned %>% 
  last_fit(data_split, metrics = metric_set(mae, rmse, rsq_trad))

The performance on the test set for this model is:

# Collect metrics from the model on the test set
lasso_test_metrics <- lasso_last_fit %>% collect_metrics()
lasso_test_metrics

As seen above, the final lasso model has mean absolute error of 0.27, root mean squared error of 0.37 and R squared on 48,7% on the test data.

To assess the importance of the predictor variables, model parameter estimates are calculated below:

# Fit the model on the training data and pull the model coefficients for the variables
lasso_wf_tuned %>% fit(data_train) %>% pull_workflow_fit() %>% tidy() 

As lasso performs subset selection automatically, some variables have a coefficient of zero. There are multiple variables with coefficient of zero, which implies that these variables are less important for the price prediction of new Airbnb listings. The most important variables can be identified by looking at the coefficients as well, and the 4 most important variables are number of accommodates, the number of days that the airbnb is available inside 30 days, room type of entire home apartment, and lastly, Centrum-West neighbourhood.

Random Forest

Random forest specification

Recipe

Within this section, a random forest will be created. First a preprocessing recipe is created. The id variable is updated to a seperate role, instead of being a predictor.

# Specify recipe
rf_recipe <- recipe(price ~ ., data = data_train) %>%
  update_role(id, new_role = "id var")

rf_recipe
Data Recipe

Inputs:

Tune specifications

Within this section the tune specification are mentioned. The mtry is the number of features that are used at each split. The exact mtry value will be tuned later on. Different values for trees where tested (200, 500 & 1000). Increasing the amount of trees did not have much impact on the results. Therefore, a tree size of 200 is chosen to save computational time.

# Tune specification
rf_tune_spec <- rand_forest(mtry = tune(), trees = 200) %>%
  set_engine("ranger") %>%
  set_mode("regression")

The recipe and the model are combined into a workflow that can be tuned.

# Workflow creation
rf_tune_wf <- workflow() %>%
  add_recipe(rf_recipe) %>%
  add_model(rf_tune_spec)

A metric set is specified, which calculates the Root Mean Square Error (RMSE), the Mean Absolute Error (MAE) and the R-squared (rsq_trad) is created.

# Class metrics specification 
class_metrics <- metric_set(rmse, mae, rsq_trad)

The command bellow allows us to do computations in parallel.

registerDoParallel()

The command grid = tibble(mtry = 1:33) was utlised, as this allows the random forest to consider all number of variables at each split. Based on the MAE criteria, a mtry of 5, 6, 7, 8 & 9 was found as the optimal solution. Afterwards, a mtry of c(1:10)) is taken that will include the optimal values, as well mtry values of 1 up until 4 and a mtry of 10. This allows us to see that the mtry is initially increased up until it reaches its optimal mtry solution.

# Define the tune grid 
rf_tunegrid <- tibble(mtry = c(1:10))
# Tune the grid
set.seed(12345)
rf_tune_res <- tune_grid(
  rf_tune_wf,
  resamples = data_folds,
  grid = rf_tunegrid,
  metrics = class_metrics
)
rf_tune_res
# Tuning results
# 10-fold cross-validation 

Selecting tuning parameters

# Collect metrics
rf_tune_res %>%
  collect_metrics()

This plot illustrates the best mtry, based on the criteria of the MAE. A lower MAE would indicate a better result, as a lower value indicates a lower error of prediction.

# Plot results all metrics
rf_tune_res %>%
  collect_metrics() %>%
  filter(.metric %in% c("rmse", "mae", "rsq_trad")) %>%
  ggplot(aes(x = mtry, y = mean, ymin = mean - std_err, ymax = mean + std_err, 
             colour = .metric)) +
  geom_errorbar() + 
  geom_line() +
  geom_point() +
  facet_grid(.metric ~ ., scales = "free_y") +
  labs(title = "Random Forest performance metrics")

# Plot the MAE based
rf_tune_res %>%
  collect_metrics() %>%
  filter(.metric == "mae") %>% 
  ggplot(aes(x = mtry, y = mean, ymin = mean - std_err, ymax = mean + std_err)) +
  geom_errorbar(colour = "red") + 
  geom_line(colour = "red") +
  geom_point(colour = "red") +
  labs(y = "mae", title = "Random Forest performance metrics")

This command will show the best mtry based on the MAE metrics.

# Find the mtry with the best MAE
rf_tune_res %>% show_best("mae")

Best model selection

The best model based on the MAE criteria is selected and eventually finalized into the workflow.

# Best model selection
best_rmse <- select_best(rf_tune_res, "mae")
final_rf <- finalize_workflow(rf_tune_wf, best_rmse)
final_rf
== Workflow ====================================================================
Preprocessor: Recipe
Model: rand_forest()

-- Preprocessor ----------------------------------------------------------------
0 Recipe Steps

-- Model -----------------------------------------------------------------------
Random Forest Model Specification (regression)

Main Arguments:
  mtry = 6
  trees = 200

Computational engine: ranger 

Test set performance

Now we can train the finalized workflow on our entire training set

# Finalize workflow on training set
final_res <- final_rf %>%
  last_fit(data_split, metrics = class_metrics)

The results based on the test set will be

# Score on test data
set.seed(54321)
final_res %>%
  collect_metrics()

Variable importance

Now we try to asses the variable importance. We will refit the model based on our previous tune parameters. We previousyly found an optimal mtry of 7, that’s why the mtry is specified as 7. However, do keep in mind that because of the random element within a random forest, that this initial value might alter. We noticed that the optimal mtry switches between 6, 7 & 8.

# Refit the model
rf_model_vi <- rand_forest(mtry = 7, trees = 200) %>%
  set_engine("ranger", importance = "permutation")

rf_vi_wf <- workflow() %>% 
  add_model(rf_model_vi) %>% 
  add_recipe(rf_recipe)

# Fit the model again
set.seed(12345)
rf_vi_fit <- rf_vi_wf %>% fit(data = data_train)

We can use the refitted model in order the gather the variable importance

# Variable importance 
rf_vi_fit %>% pull_workflow_fit() %>% vi()

The variable importance indicates that the accommodates, bedrooms and room_type are the most important variables for predicting the price. The variables which are the least important for predicting the price are bed_type, pool, and wifi. Pool and wifi actually have a negative importance, but as this is close to a value of 0, it is chosen to still include those variables.

# Plot variable importance
var_importance_plot <-
  rf_vi_fit %>%
  pull_workflow_fit() %>% vip(geom = "point", num_features = 12) +
  labs(title = "Random Forest Variable Importance") +
  theme(plot.title = element_text(hjust = 0.5)) 
rf_vi_fit
== Workflow [trained] ==========================================================
Preprocessor: Recipe
Model: rand_forest()

-- Preprocessor ----------------------------------------------------------------
0 Recipe Steps

-- Model -----------------------------------------------------------------------
Ranger result

Call:
 ranger::ranger(formula = ..y ~ ., data = data, mtry = ~7, num.trees = ~200,      importance = ~"permutation", num.threads = 1, verbose = FALSE,      seed = sample.int(10^5, 1)) 

Type:                             Regression 
Number of trees:                  200 
Sample size:                      13874 
Number of independent variables:  33 
Mtry:                             7 
Target node size:                 5 
Variable importance mode:         permutation 
Splitrule:                        variance 
OOB prediction error (MSE):       0.1278328 
R squared (OOB):                  0.5472826 
# Save plot for presentation
ggsave("plots/rf_var_importance.png", plot = var_importance_plot,
       height = 7 , width = 10)

K-Nearest-Neighbors

Set up turning grid

# Generate tuning grid for knn
knn_tune_grid <- tibble(neighbors = 1:50*2-1)

Specify a workflow

Something that should be noted for this recipe is that only numeric variables are included. This is done for the reason that categorical variables translate with difficulty to a k-nearest neighbor algorithm. The premise of prediction based on a KNN-model is that it relies exclusively on the distance between points in the data. This distance is obvious when handling numeric variables. However, when dealing with non-numeric values and variables this distance between data points cannot easily be modeled, provided they should be modeled at all. (This will have implications for determining predictions for importance and coefficients for variables, which will be addressed at the end of the section on the KNN-model).

# Specify model 
knn_mod <- 
  nearest_neighbor(neighbors = tune()) %>% 
  set_mode("regression") %>% 
  set_engine("kknn", scale=FALSE)
knn_mod
K-Nearest Neighbor Model Specification (regression)

Main Arguments:
  neighbors = tune()

Engine-Specific Arguments:
  scale = FALSE

Computational engine: kknn 
# Specify recipe
knn_recipe <- 
  recipe(price ~ ., data = data_train) %>% 
  step_rm(all_nominal()) %>%
  update_role(id, new_role = "id var") %>% 
  step_normalize(all_predictors(), -id)
knn_recipe
Data Recipe

Inputs:

Operations:

Delete terms all_nominal()
Centering and scaling for all_predictors(), -id

The normalization of the data is ensured through the following commands:

# Check normalization 
train_baked <- knn_recipe %>% prep(data_train) %>% bake(data_train)
train_baked %>% head()
round(colMeans(train_baked, 8))
                                          id                                 accommodates                                    bathrooms                                     bedrooms 
                                    19106945                                            0                                            0                                            0 
                                        beds                          host_listings_count                              guests_included                                 extra_people 
                                           0                                            0                                            0                                            0 
                              minimum_nights                               maximum_nights                              availability_30               calculated_host_listings_count 
                                           0                                            0                                            0                                            0 
 calculated_host_listings_count_entire_homes calculated_host_listings_count_private_rooms  calculated_host_listings_count_shared_rooms                            host_years_active 
                                           0                                            0                                            0                                            0 
                                       price 
                                           5 
round(apply(train_baked, 2, sd), 8)
                                          id                                 accommodates                                    bathrooms                                     bedrooms 
                                1.141721e+07                                 1.000000e+00                                 1.000000e+00                                 1.000000e+00 
                                        beds                          host_listings_count                              guests_included                                 extra_people 
                                1.000000e+00                                 1.000000e+00                                 1.000000e+00                                 1.000000e+00 
                              minimum_nights                               maximum_nights                              availability_30               calculated_host_listings_count 
                                1.000000e+00                                 1.000000e+00                                 1.000000e+00                                 1.000000e+00 
 calculated_host_listings_count_entire_homes calculated_host_listings_count_private_rooms  calculated_host_listings_count_shared_rooms                            host_years_active 
                                1.000000e+00                                 1.000000e+00                                 1.000000e+00                                 1.000000e+00 
                                       price 
                                5.313830e-01 
rm(train_baked)

Below the initial workflow for the k-nearest neighbors model is specified

# Specify workflow
knn_workflow <- 
  workflow() %>% 
  add_model(knn_mod) %>% 
  add_recipe(knn_recipe)
knn_workflow
== Workflow ====================================================================
Preprocessor: Recipe
Model: nearest_neighbor()

-- Preprocessor ----------------------------------------------------------------
2 Recipe Steps

* step_rm()
* step_normalize()

-- Model -----------------------------------------------------------------------
K-Nearest Neighbor Model Specification (regression)

Main Arguments:
  neighbors = tune()

Engine-Specific Arguments:
  scale = FALSE

Computational engine: kknn 

Tuning the number of nearest neighbours

The code below serves to specify the assessment metrics that are used. Moreover, a grid search is performed using the validation sets.

# Store metrics in variable
metrics_reg <- metric_set(rmse, mae, rsq_trad)

# Perform grid search using validation sets
knn_tune_res <- 
  knn_workflow %>% 
  tune_grid(resamples = data_folds,
            grid = knn_tune_grid, 
            metrics = metrics_reg) 

# Plot results metrics
knn_metrics_plot <- 
  knn_tune_res %>%  collect_metrics() %>% 
  ggplot(aes(x = neighbors, y = mean)) +
  geom_point(colour = "red") + geom_line(colour = "red") +
  facet_wrap(~ .metric, scale = "free_y") +
  labs(title = "KNN Performance Metrics") +
  theme(plot.title = element_text(hjust = 0.5)) 
knn_metrics_plot


autoplot(knn_tune_res)

The plot output shows some metrics that plot the mean of the performance metrics. We should aim for the MAE (mean absolute error) and RMSE (root mean square error) to be as low as possible, and the rsq_trad (R-squared) to be as high as possible. We used the MAE metric to determine the optimal k-neighbors for our model, which arrived at 51 neighbors. This can be read from the MAE graph, by looking at the corresponsing k-neighbors for the lowest mean of MAE.

Moreover, from the last plot the elbow trend can somewhat clearly be seen: the metrics reach their optimum point after which the level off and slowly increase for MAE and RMSE and decrease for rqs_trad.

The model with the optimal number of k-nearest neighbors can then be selected as follows:

# Generate best model
knn_best_model <- select_best(knn_tune_res, metric = "mae")

Finalize workflow

Below the finalized workflow is made, which automatically picks the best KNN-model defined above (which is specified by the MAE metric)

# Finalize workflow
knn_workflow_final <- 
  knn_workflow %>% 
  finalize_workflow(knn_best_model)
knn_workflow_final
== Workflow ====================================================================
Preprocessor: Recipe
Model: nearest_neighbor()

-- Preprocessor ----------------------------------------------------------------
2 Recipe Steps

* step_rm()
* step_normalize()

-- Model -----------------------------------------------------------------------
K-Nearest Neighbor Model Specification (regression)

Main Arguments:
  neighbors = 51

Engine-Specific Arguments:
  scale = FALSE

Computational engine: kknn 

Last fit

A final workflow can be set up to check the final fit. Furthermore, the performance metrics for the best KNN-model are selected and put in a table.

# Train and test the data set
knn_last_fit <- 
  knn_workflow_final %>% 
  last_fit(data_split, 
           metrics = metrics_reg)

KNN variable importance

KNN, as a method, does not come with a prediction for the importance or coefficients of variables. The reason for this has to do with the fact that prediction in a k-nearest neighbor model relies exclusively on the distance between data points. With this comes the added implication that no information about the relative importance of variables can be derived from it.

Part 3: Model Comparison

In order to assess the performance of the three models the results of three metrics are compared.

  1. Root mean squared error. The objective is to minimize the result of this metric. An implication is that the metric is very sensitive to observations with large absolute residuals.
  2. Mean absolute error. The objective is to minimize the result of this metric. This metric is more robust and therefore less sensitive to observations with large absolute residuals. However, because it uses the mean, it is therefore not insensitive to skewed distributions.
  3. R-squared. An attraction is that the metric is unitless and can therefore be compared across models. A downside is that is not robust, since it essentially measures correlation and not agreement.

Assess appropriateness metrics

In order to check if the metrics are an appropriate fit, the residuals distributions of the models are plotted. Since the plots below show no large outliers and no skewed distributions, there are no implications for root mean squared error and mean absolute error.

# Generate predicted values for sales
lasso_test_preds <- 
  lasso_wf_tuned %>% 
  fit(data = data_train) %>%
  predict(data_test) %>% 
  pull(.pred)

# Create tibble for distribution plot
lasso_pred <- 
  tibble(observed = data_test$price, 
         predicted = lasso_test_preds, 
         residual = observed - predicted)

# Plot distribution residuals
lasso_residual_plot <- 
  lasso_pred %>% 
  ggplot(aes(x = residual)) +
  geom_density(bw = 0.15, fill = "springgreen", alpha = 0.5) +
  geom_rug() +
  labs(title = "Lasso Regularized Regression Distribution Residuals") +
  theme(plot.title = element_text(hjust = 0.5)) +
  coord_cartesian(ylim = c(0, 1.5))
lasso_residual_plot

# Generate predicted values for sales
set.seed(12345)
rf_test_preds <- 
  rf_vi_wf %>% 
  fit(data = data_train) %>%
  predict(data_test) %>% 
  pull(.pred)

# Create tibble for distribution plot
rf_pred <- 
  tibble(observed = data_test$price, 
         predicted = rf_test_preds, 
         residual = observed - predicted)

# Plot distribution residuals
rf_residual_plot <- 
  rf_pred %>% 
  ggplot(aes(x = residual)) +
  geom_density(bw = 0.15, fill = "springgreen", alpha = 0.5) +
  geom_rug() +
  labs(title = "Random Forest Distribution Residuals") +
  theme(plot.title = element_text(hjust = 0.5)) +
  coord_cartesian(ylim = c(0, 1.5))
rf_residual_plot

# Generate predicted values for price
knn_test_preds <- 
  knn_workflow_final %>% 
  fit(data = data_train) %>%
  predict(data_test) %>% 
  pull(.pred)

# Create tibble for distribution plot
knn_pred <- 
  tibble(observed = data_test$price, 
         predicted = knn_test_preds, 
         residual = observed - predicted)

# Plot distribution residuals
knn_residual_plot <- 
  knn_pred %>% 
  ggplot(aes(x = residual)) +
  geom_density(bw = 0.15, fill = "springgreen", alpha = 0.5) +
  geom_rug() +
  labs(title = "KNN Distribution Residuals") +
  theme(plot.title = element_text(hjust = 0.5)) +
  coord_cartesian(ylim = c(0, 1.5))
knn_residual_plot

Assessment metrics

The table below shows results for the metrics for the three models. When assessing the metrics and their objectives, the results show that the random forest model performs best on all metrics. Therefore, the random forest is considered to be the best model.

# Generate table with 
lasso_metrics_compare <- 
  lasso_test_metrics %>% 
  select(-.estimator) %>% 
  mutate(model = "lasso regression")
rf_metrics_compare <- 
  final_res %>%
  collect_metrics() %>% 
  mutate(model = "random forest")
knn_metrics_compare <- 
  knn_last_fit %>% 
  collect_metrics %>% 
  select(-.estimator) %>% 
  mutate(model = "knn reg")
lasso_metrics_compare %>%
  bind_rows(rf_metrics_compare, knn_metrics_compare) %>% 
  select(-.estimator) %>% 
  pivot_wider(names_from = .metric, values_from = .estimate)

Part 4: Recommendations

For this assignment we assessed three models for predicting prices on the Airbnb platform. These three models are a lasso regularized linear regression, a random forest and finally a K-Nearest Neighbours model. The models are assessed on three different metrics, namely the root mean squared error (RMSE), the mean squared error (MAE) and the r-squared. The proposed assessment metrics indicate that the random forest outperforms the lasso regularized linear regression and the K-Nearest-Neighbor in all proposed metrics.

Furthermore, the variable importance of the random forest indicates which variables lead to the highest increase in R-squared. Accommodates, bedrooms and room_type are the most important variables for predicting the price. Bed_type, pool, and wifi are the least important for predicting the price. We therefore advise hosts to specifically look at the variables with a high importance, as these variables have the highest impact on their predicted price.

As the model performance metrics were used to compare the models and to select the best one, these metrics should not be used to estimate the generalization error, or how well the model would perform on completely new data. For this purpose, it is recommended that the random forest model will be further tested in an online environment before scaling up its implementation. Additionally, in practice, the model will provide the prediction in log prices, and this has to be converted to euros. For example, a log price prediction of 4.09 would reflect price of €59.74.

How are these findings of use to Airbnb? Essentially, this project has sought to examine three approaches to competitively set listing prices of Airbnb listings. Considering our results, we advise Airbnb to use a random forest model in their projects that deal with optimal pricing of listings.

LS0tDQp0aXRsZTogIk1MTEEgLSBHcm91cCBBc3NpZ25tZW50Ig0Kb3V0cHV0OiBodG1sX25vdGVib29rDQpkYXRlOiAiMTEvMjUvMjAyMCINCmF1dGhvcjogDQogIC0gR29zd2luIE5pYmJlcmluZyAtIDU2MzI4NQ0KICAtIEt5bGlhbiB2YW4gTm9vcmRlbm5lIC0gNDUwNzUyIA0KICAtIE5vb3JhIE1hdHRzc29uIC0gNDc3MTAwDQogIC0gRWxpbmUgdmFuIEdyb25pbmdlbiAtIDQxNDg0Ng0KLS0tDQoNCiMgU2V0dXAgbm90ZWJvb2sNCg0KVGhlIGZvbGxvd2luZyBsaWJyYXJpZXMgYXJlIHVzZWQgZm9yIHRoaXMgbm90ZWJvb2s6DQpgYGB7ciBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0NCiMgTG9hZCBsaWJyYXJpZXMNCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeSh0aWR5bW9kZWxzKQ0KbGlicmFyeShnbG1uZXQpDQpsaWJyYXJ5KGxlYXBzKQ0KbGlicmFyeShuYW5pYXIpDQpsaWJyYXJ5KHNraW1yKQ0KbGlicmFyeShrbml0cikNCmxpYnJhcnkoY29ycnBsb3QpDQpsaWJyYXJ5KHJhbmdlcikNCmxpYnJhcnkoZG9QYXJhbGxlbCkNCmxpYnJhcnkodGhlbWlzKQ0KbGlicmFyeSh2aXApDQpgYGANCg0KIyBMb2FkIGRhdGEgbGlzdGluZ3MNCmBgYHtyIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFfQ0KIyBSZWFkIGNzdiB3aXRoIGxpc3RpbmcgaW5mb3JtYXRpb24NCmRhdGEgPC0gcmVhZF9jc3YoZ3pmaWxlKCJsaXN0aW5ncy5jc3YuZ3oiKSkNCmBgYA0KDQojIFBhcnQgMTogRGF0YSBDbGVhbmluZyBhbmQgRmVhdHVyZSBTZWxlY3Rpb24NCg0KIyBTZWxlY3QgdmFyaWFibGVzIG9mIGludGVyZXN0DQpUaGUgZ29hbCBvZiB0aGUgYXNzaWdubWVudCBpcyB0byBidWlsZCBhIG1vZGVsIHRoYXQgcHJlZGljdHMgdGhlIHByaWNlcyBvZiBsaXN0aW5ncyBvbiBBaXJCbkIgaW4gQW1zdGVyZGFtLiBUaGUgb3V0Y29tZXMgb2YgdGhlIG1vZGVsIHdpbGwgYmUgdXNlZCBmb3Igc3VnZ2VzdGlvbnMgdG8gdGhlIG5ldyBob3N0cyBhYm91dCB0aGUgYXZlcmFnZSBwbGF0Zm9ybSBwcmljZSBmb3Igc2ltaWxhciBsaXN0aW5ncy4gQWZ0ZXJ3YXJkcywgaG9zdHMgY2FuIGNob29zZSB3aGV0aGVyIHRoZXkgd2FudCB0byB1c2UgdGhlIHJlY29tbWVuZGF0aW9uIHRvIHNldCB0aGVpciBwcmljZXMgYWNjb3JkaW5nbHkgaW4gb3JkZXIgdG8gYmUgY29tcGV0aXRpdmUgYW5kIGdhaW4gYXR0ZW50aW9uIGZyb20gdGhlIGd1ZXN0cyBzaW5jZSB0aGUgYmVnaW5uaW5nLiBBbGwgdmFyaWFibGVzIGluY2x1ZGluZyBpbmZvcm1hdGlvbiBvbiB0aGUgcmV2aWV3cyBwcm92aWRlIGluZm9ybWF0aW9uIGFib3V0IGEgbGlzdGluZyBhZnRlciBpdCBoYXMgYmVlbiBwdWJsaXNoZWQuIFRoZXJlZm9yZSwgdGhlc2UgdmFyaWFibGVzIGFyZSBub3QgaW5jbHVkZWQgaW4gdGhlIGRhdGEgc2V0LiBNb3Jlb3ZlciwgdGhlIHZhcmlhYmxlcyBpbmNsdWRpbmcgYSBkZXNjcmlwdGlvbiBhbmQgc3VtbWFyeSBhYm91dCB0aGUgbGlzdGluZyBjYW4gYmUgYW5hbHl6ZWQgdXNpbmcgTkxQIChlLmcuIHNlbnRpbWVudCBhbmFseXNpcykuIEhvd2V2ZXIsIHRoaXMgaXMgYmV5b25kIHRoZSBzY29wZSBvZiB0aGUgYXNzaWdubWVudC4gVGhlcmVmb3JlLCB0aGVzZSB2YXJpYWJsZXMgYXJlIGV4Y2x1ZGVkIGZyb20gdGhlIG1vZGVsLiBUaGUgdmFyaWFibGVzIGJlbG93IGFyZSBpbmNsdWRlZCBpbiB0aGUgZGF0YSBzZXQgZm9yIGZ1cnRoZXIgYW5hbHlzaXMgYW5kIGNsZWFuaW5nLg0KDQpgYGB7ciBtZXNzYWdlID0gRkFMU0V9DQojIEdlbmVyYXRlIHN1YnNldCB3aXRoIHZhcmlhYmxlcyBvZiBpbnRlcmVzdA0KZGF0YV9zdWIgPC0gZGF0YSAlPiUNCiAgc2VsZWN0KGlkLCBwcmljZSwgcHJvcGVydHlfdHlwZSwgcm9vbV90eXBlLCBhY2NvbW1vZGF0ZXMsIGJhdGhyb29tcywgYmVkcm9vbXMsDQogICAgICAgICBiZWRzLCBiZWRfdHlwZSwgYW1lbml0aWVzLCBob3N0X3NpbmNlLCBob3N0X3Jlc3BvbnNlX3RpbWUsDQogICAgICAgICBob3N0X3Jlc3BvbnNlX3JhdGUsIGhvc3RfbmVpZ2hib3VyaG9vZCwgaG9zdF9saXN0aW5nc19jb3VudCwgDQogICAgICAgICBob3N0X3ZlcmlmaWNhdGlvbnMsIGhvc3RfaWRlbnRpdHlfdmVyaWZpZWQsIG5laWdoYm91cmhvb2RfY2xlYW5zZWQsDQogICAgICAgICBzcXVhcmVfZmVldCwgY2xlYW5pbmdfZmVlLCBndWVzdHNfaW5jbHVkZWQsIGV4dHJhX3Blb3BsZSwgDQogICAgICAgICBtaW5pbXVtX25pZ2h0cywgbWF4aW11bV9uaWdodHMsIGF2YWlsYWJpbGl0eV8zMCwgYXZhaWxhYmlsaXR5XzYwLA0KICAgICAgICAgYXZhaWxhYmlsaXR5XzkwLCBhdmFpbGFiaWxpdHlfMzY1LCBpbnN0YW50X2Jvb2thYmxlLCANCiAgICAgICAgIGNhbmNlbGxhdGlvbl9wb2xpY3ksIHJlcXVpcmVfZ3Vlc3RfcHJvZmlsZV9waWN0dXJlLA0KICAgICAgICAgcmVxdWlyZV9ndWVzdF9waG9uZV92ZXJpZmljYXRpb24sIGNhbGN1bGF0ZWRfaG9zdF9saXN0aW5nc19jb3VudCwNCiAgICAgICAgIGNhbGN1bGF0ZWRfaG9zdF9saXN0aW5nc19jb3VudF9lbnRpcmVfaG9tZXMsIA0KICAgICAgICAgY2FsY3VsYXRlZF9ob3N0X2xpc3RpbmdzX2NvdW50X3ByaXZhdGVfcm9vbXMsDQogICAgICAgICBjYWxjdWxhdGVkX2hvc3RfbGlzdGluZ3NfY291bnRfc2hhcmVkX3Jvb21zKQ0KYGBgDQoNCmBgYHtyfQ0KIyBJbnNwZWN0IGRhdGENCmhlYWQoZGF0YV9zdWIpDQpgYGANCg0KYGBge3J9DQojIEluc3BlY3QgZGF0YQ0Kc2tpbShkYXRhX3N1YikgJT4lIGtuaXRfcHJpbnQoKQ0KYGBgDQoNCiMgRGF0YSBjbGVhbmluZw0KDQojIyBCYXNpYyBjbGVhbmluZw0KDQpGaXJzdCwgd2UgY29udmVydGVkIGFsbCBjYXRlZ29yaWNhbCBhbmQgbG9naWNhbCB2YXJpYWJsZXMsIHdoaWNoIGRpZCBub3QgbmVlZCBhbnkgZnVydGhlciBjbGVhbmluZywgdG8gZGF0YSB0eXBlIGZhY3Rvci4NCmBgYHtyIENvbnZlcnRpbmcgdmVjdG9yc30NCiMgQ29udmVydCBjYXRlZ29yaWNhbCB2YXJzIHRvIGZhY3RvcnMgDQpkYXRhX3N1YiRwcm9wZXJ0eV90eXBlIDwtIGZhY3RvcihkYXRhX3N1YiRwcm9wZXJ0eV90eXBlICwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsZXZlbHMgPSB1bmlxdWUoZGF0YV9zdWIkcHJvcGVydHlfdHlwZSkpDQpkYXRhX3N1YiRyb29tX3R5cGUgPC0gZmFjdG9yKGRhdGFfc3ViJHJvb21fdHlwZSAsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsZXZlbHMgPSB1bmlxdWUoZGF0YV9zdWIkcm9vbV90eXBlKSkNCmRhdGFfc3ViJGJlZF90eXBlIDwtIGZhY3RvcihkYXRhX3N1YiRiZWRfdHlwZSAsIA0KICAgICAgICAgICAgICAgICAgICBsZXZlbHMgPSB1bmlxdWUoZGF0YV9zdWIkYmVkX3R5cGUpKQ0KZGF0YV9zdWIkaG9zdF9yZXNwb25zZV90aW1lIDwtIGZhY3RvcihkYXRhX3N1YiQgaG9zdF9yZXNwb25zZV90aW1lLCANCiAgICAgICAgICAgICAgICAgICAgbGV2ZWxzID0gdW5pcXVlKGRhdGFfc3ViJGhvc3RfcmVzcG9uc2VfdGltZSkpDQpkYXRhX3N1YiRob3N0X25laWdoYm91cmhvb2QgPC0gZmFjdG9yKGRhdGFfc3ViJGhvc3RfbmVpZ2hib3VyaG9vZCwgDQogICAgICAgICAgICAgICAgICAgIGxldmVscyA9IHVuaXF1ZShkYXRhX3N1YiRob3N0X25laWdoYm91cmhvb2QpKQ0KZGF0YV9zdWIkbmVpZ2hib3VyaG9vZF9jbGVhbnNlZCA8LSBmYWN0b3IoZGF0YV9zdWIkbmVpZ2hib3VyaG9vZF9jbGVhbnNlZCwgDQogICAgICAgICAgICAgICAgICAgIGxldmVscyA9IHVuaXF1ZShkYXRhX3N1YiRuZWlnaGJvdXJob29kX2NsZWFuc2VkKSkNCmRhdGFfc3ViJGNhbmNlbGxhdGlvbl9wb2xpY3kgPC0gZmFjdG9yKGRhdGFfc3ViJGNhbmNlbGxhdGlvbl9wb2xpY3kgLCANCiAgICAgICAgICAgICAgICAgICAgbGV2ZWxzID0gdW5pcXVlKGRhdGFfc3ViJGNhbmNlbGxhdGlvbl9wb2xpY3kpKQ0KDQojIENvbnZlcnQgbG9naWNhbCB2YXJpYWJsZXMgdG8gZmFjdG9ycw0KZGF0YV9zdWIkaG9zdF9pZGVudGl0eV92ZXJpZmllZCA8LSBmYWN0b3IoZGF0YV9zdWIkaG9zdF9pZGVudGl0eV92ZXJpZmllZCkNCmRhdGFfc3ViJGluc3RhbnRfYm9va2FibGUgPC0gZmFjdG9yKGRhdGFfc3ViJGluc3RhbnRfYm9va2FibGUpDQpkYXRhX3N1YiRyZXF1aXJlX2d1ZXN0X3Byb2ZpbGVfcGljdHVyZSA8LSANCiAgZmFjdG9yKGRhdGFfc3ViJHJlcXVpcmVfZ3Vlc3RfcHJvZmlsZV9waWN0dXJlKQ0KZGF0YV9zdWIkcmVxdWlyZV9ndWVzdF9waG9uZV92ZXJpZmljYXRpb24gPC0gDQogIGZhY3RvcihkYXRhX3N1YiRyZXF1aXJlX2d1ZXN0X3Bob25lX3ZlcmlmaWNhdGlvbikNCmBgYA0KDQpTZWNvbmQsIHNvbWUgb2YgdGhlIHZhcmlhYmxlcyBjb250YWluIG51bWVyaWMgdmFyaWFibGVzLCBob3dldmVyLCB0aGV5IGFyZSBzdG9yZWQgaW4gYSBzdHJpbmcgY29udGFpbmluZyBhIGRvbGxhciBvciBwZXJjZW50YWdlIHNpZ24uIFRoZSBzaWducyB3ZXJlIHJlbW92ZWQgZnJvbSB0aGUgc3RyaW5ncywgYW5kIHRoZSByZW1haW5pbmcgbnVtYmVycyB3ZXJlIGNvbnZlcnRlZCB0byBudW1lcmljIHZhcmlhYmxlcy4NCmBgYHtyIENvbnZlcnQgfQ0KIyBSZW1vdmUgJCBzaWduIGZyb20gY29sdW1ucyBjb250YWluaW5nIHByaWNlcyBhbmQgY29udmVydCB0byBkb3VibGVzDQpkYXRhX3N1YiRwcmljZSA8LSBhcy5kb3VibGUoZ3N1YigiWywkXSIsICIiLCBkYXRhX3N1YiRwcmljZSkpDQpkYXRhX3N1YiRjbGVhbmluZ19mZWUgPC0gYXMuZG91YmxlKGdzdWIoIlssJF0iLCAiIiwgZGF0YV9zdWIkY2xlYW5pbmdfZmVlKSkNCmRhdGFfc3ViJGV4dHJhX3Blb3BsZSA8LSBhcy5kb3VibGUoZ3N1YigiWywkXSIsICIiLCBkYXRhX3N1YiRleHRyYV9wZW9wbGUpKQ0KDQojIFJlcGxhY2UgIk4vQSIgdmFsdWVzLCByZW1vdmUgJSBhbmQgY29udmVydCB0byBwZXJjZW50YWdlIA0KZGF0YV9zdWIkaG9zdF9yZXNwb25zZV9yYXRlIDwtIG5hX2lmKGRhdGFfc3ViJGhvc3RfcmVzcG9uc2VfcmF0ZSwgIk4vQSIpDQpkYXRhX3N1YiRob3N0X3Jlc3BvbnNlX3JhdGUgPC0gDQogIGFzLmRvdWJsZShnc3ViKCJbJV0iLCAiIiwgZGF0YV9zdWIkaG9zdF9yZXNwb25zZV9yYXRlKSkgLyAxMDANCmBgYA0KDQojIyBDbGVhbiBhbWVuaXRpZXMgDQoNClRoZSB2YXJpYWJsZSAqYW1lbml0aWVzKiBjb250YWlucyBhbGwgdGhlIGFtZW5pdGllcyBvZiB0aGUgbGlzdGluZy4gSG93ZXZlciwgdGhpcyB3YXMgc3RvcmVkIGluIG9uZSBsYXJnZSBzdHJpbmcsIGFuZCB0aGUgZWxlbWVudHMgY291bGQgbm90IGJlIGFjY2Vzc2VkIHNlcGFyYXRlbHkuIFRoZXJlZm9yZSwgd2UgY2xlYW5lZCB0aGUgc3RyaW5nIGFuZCBzcGxpdHRlZCBpdCB0byBhIGxpc3QgY29udGFpbmluZyB0aGUgc2VwYXJhdGVkIGVsZW1lbnRzLiBGdXJ0aGVybW9yZSwgd2UgZXh0cmFjdGVkIGFsbCB1bmlxdWUgYW1lbml0aWVzIGFuZCBzdG9yZWQgdGhlc2UgaW4gYSB2ZWN0b3IuIA0KYGBge3J9DQojIENsZWFuIGFuZCBzcGxpdCBzdHJpbmdzIGZvciBhbWVuaXRpZXMNCiMgUmV0dXJucyBhIGxpc3Qgd2l0aCBhbGwgdW5pcXVlIHZhbHVlcw0KY2xlYW5fYW1lbml0aWVzIDwtIGZ1bmN0aW9uKHgpIHsNCiAgc3ViYmVkIDwtIGdzdWIoJ1t7fVwiXScsICIiLCB0b2xvd2VyKHgpKQ0KICBzcGxpdHRlZCA8LSBzdHJfc3BsaXQoc3ViYmVkLCAiLCIpDQogIGNsZWFuIDwtIHNhcHBseShzcGxpdHRlZCwgZnVuY3Rpb24oeCkgc3RyX3RyaW0oeCwgc2lkZSA9ICJib3RoIikpDQogIHJldHVybihjbGVhbikNCn0NCg0KIyBDbGVhbiBhbWVuaXRpZXMNCmRhdGFfc3ViJGFtZW5pdGllc19jbGVhbiA8LSANCiAgc2FwcGx5KGRhdGFfc3ViJGFtZW5pdGllcywgZnVuY3Rpb24oeCkgY2xlYW5fYW1lbml0aWVzKHgpKQ0KDQojIENyZWF0ZSB2ZWN0b3Igd2l0aCBhbGwgdW5pcXVlIGFtZW5pdGllcw0KYW1lbml0aWVzX3VuaXF1ZSA9IGMoKQ0KZm9yKGFtZW5pdGllcyBpbiBkYXRhX3N1YiRhbWVuaXRpZXNfY2xlYW4pIHsNCiAgZm9yKGVsZW1lbnQgaW4gYW1lbml0aWVzKSB7DQogICAgaWYoIShlbGVtZW50ICVpbiUgYW1lbml0aWVzX3VuaXF1ZSkgJiBlbGVtZW50ICE9ICIiKSB7DQogICAgICBhbWVuaXRpZXNfdW5pcXVlIDwtIGFwcGVuZChhbWVuaXRpZXNfdW5pcXVlLCBzdHJfdHJpbShlbGVtZW50KSkNCiAgICB9DQogIH0NCn0NCmFtZW5pdGllc191bmlxdWUNCmBgYA0KDQojIyMgQ3JlYXRlIG5ldyB2YXJpYWJsZXMgYmFzZWQgaW5mb3JtYXRpb24gc3RvcmVkIGluIGFtZW5pdGllcw0KDQpTZXBhcmF0ZSB2YXJpYWJsZXMgY291bGQgYmUgY3JlYXRlZCBmcm9tIHRoZSB2ZWN0b3IgY29udGFpbmluZyBhbGwgdW5pcXVlIGFtZW5pdGllcy4gIEhvd2V2ZXIsIHNpbmNlIHRoZXJlIGFyZSAxMzAgdXNhYmxlIGFtZW5pdGllcyBpdCBzZWVtZWQgYmV5b25kIHRoZSBzY29wZSBvZiB0aGUgYXNzaWdubWVudC4gTW9yZW92ZXIsIHNvbWUgb2YgdGhlIGFtZW5pdGllcyBjb250YWluIGluZm9ybWF0aW9uIHRoYXQgaXMgYWxzbyBnaXZlbiBieSBvdGhlciB2YXJpYWJsZXMgb3IgYWJvdXQgb3RoZXIgYW1lbml0aWVzLiBGb3IgZXhhbXBsZSBhIHByaXZhdGUgYmF0aHJvb20gY291bGQgYWxzbyBiZSBhIHN0cm9uZyBpbmRpY2F0b3IgdGhhdCB0aGUgbGlzdGluZyBpcyBhbiBlbnRpcmUgaG91c2UvYXBhcnRtZW50LiBBbHNvLCBzaGFtcG9vIG9yIHNob3dlciBnZWwgY291bGQgYmUgc3Ryb25nIGluZGljYXRvcnMgZm9yIHRoZSBwcmVzZW5jZSBvZiBhIGJhdGhyb29tLiBGdXJ0aGVybW9yZSwgc29tZSBhbWVuaXRpZXMgYXJlIHZlcnkgc3BlY2lmaWMgYW5kIGFwcGx5IG9ubHkgdG8gYSBmZXcgb3Igb25lIGhvdXNlLiBZZXQsIHZhcmlhYmxlcyBhcmUgY3JlYXRlZCBmb3Igc29tZSBvZiB0aGUgYW1lbml0aWVzIHRoYXQgY291bGQgaGF2ZSBhbiBpbmZsdWVuY2Ugb24gdGhlIHByaWNlIG9mIGEgbGlzdGluZy4gV2UgY3JlYXRlZCB2YXJpYWJsZXMgZm9yICp3aWZpKiwgKnBvb2wqLCAqaG90X3R1YiogYW5kICp0diouIA0KYGBge3IgQ3JlYXRlIG5ldyB2YXJpYWJsZXMgZm9yIGFtZW5pdGllc30NCiMgQ3JlYXRlIHZhcmlhYmxlIGZvciBXSUZJIGFuZCBhZGQgdG8gZGF0YSBzZXQNCndpZmkgPC0gdmVjdG9yKCkNCmZvcihpIGluIDE6bGVuZ3RoKGRhdGFfc3ViJGFtZW5pdGllc19jbGVhbikpIHsNCiAgaWYoIndpZmkiICVpbiUgZGF0YV9zdWIkYW1lbml0aWVzX2NsZWFuW1tpXV0gfCANCiAgICAgImludGVybmV0IiAlaW4lIGRhdGFfc3ViJGFtZW5pdGllc19jbGVhbltbaV1dKSB7DQogICAgd2lmaVtpXSA8LSAgInllcyINCiAgfSBlbHNlIHsNCiAgICB3aWZpW2ldIDwtICAibm8iDQogIH0NCn0NCmRhdGFfc3ViJHdpZmkgPC0gd2lmaQ0KZGF0YV9zdWIkd2lmaSA8LSBmYWN0b3IoZGF0YV9zdWIkd2lmaSwgbGV2ZWxzID0gYygieWVzIiwgIm5vIikpDQoNCiMgQ3JlYXRlIHZhcmlhYmxlIGZvciBwb29sIGFuZCBhZGQgdG8gZGF0YSBzZXQNCnBvb2wgPC0gdmVjdG9yKCkNCmZvcihpIGluIDE6bGVuZ3RoKGRhdGFfc3ViJGFtZW5pdGllc19jbGVhbikpIHsNCiAgaWYoInBvb2wiICVpbiUgZGF0YV9zdWIkYW1lbml0aWVzX2NsZWFuW1tpXV0gfA0KICAgICAicG9vbCB3aXRoIHBvb2wgaG9pc3QiICVpbiUgZGF0YV9zdWIkYW1lbml0aWVzX2NsZWFuW1tpXV0pIHsNCiAgICBwb29sW2ldIDwtICAieWVzIg0KICB9IGVsc2Ugew0KICAgIHBvb2xbaV0gPC0gICJubyINCiAgfQ0KfQ0KZGF0YV9zdWIkcG9vbCA8LSBwb29sDQpkYXRhX3N1YiRwb29sIDwtIGZhY3RvcihkYXRhX3N1YiRwb29sLCBsZXZlbHMgPSBjKCJ5ZXMiLCAibm8iKSkNCg0KIyBDcmVhdGUgdmFyaWFibGUgZm9yIGhvdF90dWIgYW5kIGFkZCB0byBkYXRhIHNldA0KaG90X3R1YiA8LSB2ZWN0b3IoKQ0KZm9yKGkgaW4gMTpsZW5ndGgoZGF0YV9zdWIkYW1lbml0aWVzX2NsZWFuKSkgew0KICBpZigiaG90IHR1YiIgJWluJSBkYXRhX3N1YiRhbWVuaXRpZXNfY2xlYW5bW2ldXSkgew0KICAgIGhvdF90dWJbaV0gPC0gICJ5ZXMiDQogIH0gZWxzZSB7DQogICAgaG90X3R1YltpXSA8LSAgIm5vIg0KICB9DQp9DQpkYXRhX3N1YiRob3RfdHViIDwtIGhvdF90dWINCmRhdGFfc3ViJGhvdF90dWIgPC0gZmFjdG9yKGRhdGFfc3ViJGhvdF90dWIsIGxldmVscyA9IGMoInllcyIsICJubyIpKQ0KDQojIENyZWF0ZSB2YXJpYWJsZSBmb3IgaG90X3R1YiBhbmQgYWRkIHRvIGRhdGEgc2V0DQp0diA8LSB2ZWN0b3IoKQ0KZm9yKGkgaW4gMTpsZW5ndGgoZGF0YV9zdWIkYW1lbml0aWVzX2NsZWFuKSkgew0KICBpZigidHYiICVpbiUgZGF0YV9zdWIkYW1lbml0aWVzX2NsZWFuW1tpXV0gfA0KICAgICAiY2FibGUgdHYiICVpbiUgZGF0YV9zdWIkYW1lbml0aWVzX2NsZWFuW1tpXV0pIHsNCiAgICB0dltpXSA8LSAgInllcyINCiAgfSBlbHNlIHsNCiAgICB0dltpXSA8LSAgIm5vIg0KICB9DQp9DQpkYXRhX3N1YiR0diA8LSB0dg0KZGF0YV9zdWIkdHYgPC0gZmFjdG9yKGRhdGFfc3ViJHR2LCBsZXZlbHMgPSBjKCJ5ZXMiLCAibm8iKSkNCmBgYA0KDQojIyBDbGVhbiBob3N0IHZlcmlmaWNhdGlvbiBtZXRob2RzDQoNClRoZSBzYW1lIHJlYXNvbmluZyBmcm9tIHRoZSAqYW1lbml0aWVzKiBzZWN0aW9uIGFib3ZlIGFwcGxpZXMgdG8gdGhlIHZhcmlhYmxlICpob3N0X3ZlcmlmaWNhdGlvbiouIFRoZSBzYW1lIGNsZWFuaW5nIG1ldGhvZCB3YXMgdXNlZCBhcyBmb3IgYW1lbml0aWVzLCBmaXJzdCB3ZSBjbGVhbmVkIGFuZCBzcGxpdHRlZCB0aGUgc3RyaW5ncywgdGhlcmVhZnRlciBhIHZlY3RvciB3aXRoIGFsbCB1bmlxdWUgaG9zdCB2ZXJpZmljYXRpb24gbWV0aG9kcyBpcyBnZW5lcmF0ZWQuDQpgYGB7ciBHZW5lcmF0ZSB1bmlxdWUgaG9zdCB2ZXJpZmljYXRpb24gbWV0aG9kc30NCiMgQ2xlYW4gYW5kIHNwbGl0IHN0cmluZ3MgZm9yIGhvc3QgdmVyaWZpY2F0aW9uIG1ldGhvZHMNCiMgUmV0dXJucyBhIGxpc3Qgd2l0aCBhbGwgdW5pcXVlIHZhbHVlcw0KY2xlYW5fdmVyZmljaWF0aW9ucyA8LSBmdW5jdGlvbih4KSB7DQogIHN1YmJlZCA8LSBnc3ViKCJcXFt8XFxdIiwgIiIsIHRvbG93ZXIoeCkpDQogIHN1YmJlZF9jb21wbGV0ZSA8LSBnc3ViKCJbJ10iLCAiIiwgc3ViYmVkKQ0KICBzcGxpdHRlZCA8LSBzdHJfc3BsaXQoc3ViYmVkX2NvbXBsZXRlLCAiLCIpDQogIGNsZWFuIDwtIHNhcHBseShzcGxpdHRlZCwgZnVuY3Rpb24oeCkgc3RyX3RyaW0oeCwgc2lkZSA9ICJib3RoIikpDQogIHJldHVybihjbGVhbikNCn0NCg0KIyBDbGVhbiBob3N0X3ZlcmlmaWNhdGlvbnMNCmRhdGFfc3ViJGhvc3RfdmVyaWZpY2F0aW9uc19jbGVhbiA8LSANCiAgc2FwcGx5KGRhdGFfc3ViJGhvc3RfdmVyaWZpY2F0aW9ucywgZnVuY3Rpb24oeCkgY2xlYW5fdmVyZmljaWF0aW9ucyh4KSkNCg0KIyBHZW5lcmF0ZSBsaXN0IHdpdGggYWxsIHVuaXF1ZSBob3N0IHZlcmlmaWNhdGlvbiBtZXRob2RzDQp2ZXJpZmljYXRpb25zX3VuaXF1ZSA9IGMoKQ0KZm9yKHZlcmlmaWNhdGlvbnMgaW4gZGF0YV9zdWIkaG9zdF92ZXJpZmljYXRpb25zX2NsZWFuKSB7DQogIGZvcihlbGVtZW50IGluIHZlcmlmaWNhdGlvbnMpIHsNCiAgICBpZighKGVsZW1lbnQgJWluJSB2ZXJpZmljYXRpb25zX3VuaXF1ZSkgJiBlbGVtZW50ICE9ICIiKSB7DQogICAgICB2ZXJpZmljYXRpb25zX3VuaXF1ZSA8LSBhcHBlbmQodmVyaWZpY2F0aW9uc191bmlxdWUsIHN0cl90cmltKGVsZW1lbnQpKQ0KICAgIH0NCiAgfQ0KfQ0KdmVyaWZpY2F0aW9uc191bmlxdWUNCmBgYA0KDQojIyMgQ3JlYXRlIHZhcmlhYmxlcyBiYXNlZCBvbiBpbmZvcm1hdGlvbiBzdG9yZWQgaW4gaG9zdCB2ZXJpZmljYXRpb25zDQoNClNlcGFyYXRlIHZhcmlhYmxlcyBhcmUgY3JlYXRlZCBmb3IgdGhlIG1vc3QgY29tbW9uIG1ldGhvZHMgb2YgdmVyaWZpY2F0aW9uLCBuYW1lbHkgKmVtYWlsKiwgKnBob25lKiwgKmZhY2Vib29rKiBhbmQgKmdvdmVybm1lbnRfaWQqLiANCmBgYHtyIENyZWF0ZSBuZXcgdmFyaWFibGVzIGZvciBob3N0IHZlcmlmaWNhdGlvbiBtZXRob2R9DQojIENyZWF0ZSB2YXJpYWJsZSBmb3IgaG9zdCBlbWFpbCBhbmQgYWRkIHRvIGRhdGEgc2V0DQpob3N0X2VtYWlsIDwtIHZlY3RvcigpDQpmb3IoaSBpbiAxOmxlbmd0aChkYXRhX3N1YiRob3N0X3ZlcmlmaWNhdGlvbnNfY2xlYW4pKSB7DQogIGlmKCJlbWFpbCIgJWluJSBkYXRhX3N1YiRob3N0X3ZlcmlmaWNhdGlvbnNfY2xlYW5bW2ldXSkgew0KICAgIGhvc3RfZW1haWxbaV0gPC0gICJ5ZXMiDQogIH0gZWxzZSB7DQogICAgaG9zdF9lbWFpbFtpXSA8LSAgIm5vIg0KICB9DQp9DQpkYXRhX3N1YiRob3N0X2VtYWlsIDwtIGhvc3RfZW1haWwgDQpkYXRhX3N1YiRob3N0X2VtYWlsIDwtIGZhY3RvcihkYXRhX3N1YiRob3N0X2VtYWlsLCBsZXZlbHMgPSBjKCJ5ZXMiLCAibm8iKSkNCg0KIyBDcmVhdGUgdmFyaWFibGUgZm9yIHBob25lIGFuZCBhZGQgdG8gZGF0YSBzZXQgDQpob3N0X3Bob25lIDwtIHZlY3RvcigpDQpmb3IoaSBpbiAxOmxlbmd0aChkYXRhX3N1YiRob3N0X3ZlcmlmaWNhdGlvbnNfY2xlYW4pKSB7DQogIGlmKCJwaG9uZSIgJWluJSBkYXRhX3N1YiRob3N0X3ZlcmlmaWNhdGlvbnNfY2xlYW5bW2ldXSkgew0KICAgIGhvc3RfcGhvbmVbaV0gPC0gICJ5ZXMiDQogIH0gZWxzZSB7DQogICAgaG9zdF9waG9uZVtpXSA8LSAgIm5vIg0KICB9DQp9DQpkYXRhX3N1YiRob3N0X3Bob25lIDwtIGhvc3RfcGhvbmUgDQpkYXRhX3N1YiRob3N0X3Bob25lIDwtIGZhY3RvcihkYXRhX3N1YiRob3N0X3Bob25lLCBsZXZlbHMgPSBjKCJ5ZXMiLCAibm8iKSkNCiANCiMgQ3JlYXRlIHZhcmlhYmxlIGZvciBob3N0IGZhY2Vib29rIGFuZCBhZGQgdG8gZGF0YSBzZXQNCmhvc3RfZmFjZWJvb2sgPC0gdmVjdG9yKCkNCmZvcihpIGluIDE6bGVuZ3RoKGRhdGFfc3ViJGhvc3RfdmVyaWZpY2F0aW9uc19jbGVhbikpIHsNCiAgaWYoImZhY2Vib29rIiAlaW4lIGRhdGFfc3ViJGhvc3RfdmVyaWZpY2F0aW9uc19jbGVhbltbaV1dKSB7DQogICAgaG9zdF9mYWNlYm9va1tpXSA8LSAgInllcyINCiAgfSBlbHNlIHsNCiAgICBob3N0X2ZhY2Vib29rW2ldIDwtICAibm8iDQogIH0NCn0NCmRhdGFfc3ViJGhvc3RfZmFjZWJvb2sgPC0gaG9zdF9mYWNlYm9vayANCmRhdGFfc3ViJGhvc3RfZmFjZWJvb2sgPC0gDQogIGZhY3RvcihkYXRhX3N1YiRob3N0X2ZhY2Vib29rLCBsZXZlbHMgPSBjKCJ5ZXMiLCAibm8iKSkNCg0KIyBDcmVhdGUgdmFyaWFibGUgZm9yIGdvdmVybm1lbnQgaWQgDQpob3N0X2dvdmVybm1lbnRfaWQgPC0gdmVjdG9yKCkNCmZvcihpIGluIDE6bGVuZ3RoKGRhdGFfc3ViJGhvc3RfdmVyaWZpY2F0aW9uc19jbGVhbikpIHsNCiAgaWYoImdvdmVybm1lbnRfaWQiICVpbiUgZGF0YV9zdWIkaG9zdF92ZXJpZmljYXRpb25zX2NsZWFuW1tpXV0pIHsNCiAgICBob3N0X2dvdmVybm1lbnRfaWRbaV0gPC0gICJ5ZXMiDQogIH0gZWxzZSB7DQogICAgaG9zdF9nb3Zlcm5tZW50X2lkW2ldIDwtICAibm8iDQogIH0NCn0NCmRhdGFfc3ViJGhvc3RfZ292ZXJubWVudF9pZCA8LSBob3N0X2dvdmVybm1lbnRfaWQgDQpkYXRhX3N1YiRob3N0X2dvdmVybm1lbnRfaWQgPC0gDQogIGZhY3RvcihkYXRhX3N1YiRob3N0X2dvdmVybm1lbnRfaWQsIGxldmVscyA9IGMoInllcyIsICJubyIpKQ0KYGBgDQoNCiMjIENsZWFuIGRhdGUgdmFyaWFibGVzDQoNCldlIHVzZWQgdGhlIHZhcmlhYmxlICpob3N0X3NpbmNlKiB0byBjcmVhdGUgYSBuZXcgdmFyaWFibGUgKmhvc3RfeWVhcnNfYWN0aXZlKiwgd2hpY2ggY29udGFpbnMgaW5mb3JtYXRpb24gcmVnYXJkaW5nIHRoZSBudW1iZXIgb2YgeWVhcnMgYSBob3N0IGhhcyBiZWVuIGFjdGl2ZSBvbiB0aGUgcGxhdGZvcm0uIA0KYGBge3IgQ3JlYXRlIG5ldyB2YXJpYWJsZX0NCiMgQ3JlYXRlIG5ldyB2YXJpYWJsZSBmb3IgYWN0aXZlIHllYXJzIGhvc3QgDQpkYXRhX3N1YiA8LSBkYXRhX3N1YiAlPiUgDQogIG11dGF0ZShob3N0X3llYXJzX2FjdGl2ZSA9IA0KICAgICAgICAgICBhcy5kb3VibGUoYXMuRGF0ZSgiMjAxOS0xMi0wNyIpIC0gaG9zdF9zaW5jZSkgLyAzNjUpDQpgYGANCg0KIyMgSW5zcGVjdCBhdmFpbGFiaWxpdHkgdmFyaWFibGVzDQoNClRoZSB2YXJpYWJsZXMgKmF2YWlsYWJpbGl0eV8zMCosICphdmFpbGFiaWxpdHlfNjAqLCAqYXZhaWxhYmlsaXR5XzkwKiBhbmQgKmF2YWlsYWJpbGl0eV8zNjUqIGNhcnJ5IHNvbWUgb2YgdGhlIHNhbWUgaW5mb3JtYXRpb24uIEluIG9yZGVyIHRvIGluc3BlY3QgaWYgYWxsIHZhcmlhYmxlcyBzaG91bGQgYmUgaW5jbHVkZWQgaW4gdGhlIGRhdGEgc2V0LCB3ZSBwbG90dGVkIGEgY29ycmVsYXRpb24gbWF0cml4LiBUaGUgcGxvdCBiZWxvdyBzaG93cyB0aGF0IGFsbCB2YXJpYWJsZXMgaW5kaWNhdGluZyB0aGUgYXZhaWxhYmlsaXR5IGFyZSBzdHJvbmdseSBjb3JyZWxhdGVkLiBUaGVyZWZvcmUsIG9ubHkgdGhlIHZhcmlhYmxlICphdmFpbGFiaWxpdHlfMzAqIGlzIGluY2x1ZGVkIGZvciBmdXJ0aGVyIGFuYWx5c2lzLiANCmBgYHtyfQ0KIyBQbG90IGNvcnJlbGF0aW9uIG1hdHJpeA0KZGF0YV9zdWIgJT4lIHNlbGVjdF9pZihpcy5udW1lcmljKSAlPiUgDQogIHNlbGVjdChhdmFpbGFiaWxpdHlfMzAsIGF2YWlsYWJpbGl0eV82MCwgYXZhaWxhYmlsaXR5XzkwLCBhdmFpbGFiaWxpdHlfMzY1KSAlPiUgDQogIGNvcigpICU+JSBjb3JycGxvdCgpDQoNCiMgUmVtb3ZlIG90aGVyIGF2YWlsYWJpbGl0eSB2YXJpYWJsZXMgZnJvbSBkYXRhIHNldA0KZGF0YV9zdWIgPC0gDQogIGRhdGFfc3ViICU+JSANCiAgc2VsZWN0KC1hdmFpbGFiaWxpdHlfNjAsIC1hdmFpbGFiaWxpdHlfOTAsIC1hdmFpbGFiaWxpdHlfMzY1KSANCmBgYA0KDQojIyBDaGVjayBtaXNzaW5nIGRhdGENCg0KSW4gb3JkZXIgdG8gaW5zcGVjdCB3aGljaCB2YXJpYWJsZXMgaGF2ZSBtaXNzaW5nIGNhc2VzLCBhbmQgaG93IG1hbnkgdGhlcmUgYXJlIGluIGdlbmVyYWwsIGEgdGFibGUgaXMgY29uc3RydWN0ZWQuIFRoZSB0YWJsZSBzaG93cyB0aGUgdmFyaWFibGVzIGluIHRoZSBkYXRhIHNldCB3aGljaCBjb250YWluIG1pc3NpbmcgdmFsdWVzIChpbiBkZXNjZW5kaW5nIG9yZGVyKS4gVGhlIHRhYmxlIHNob3dzIHRoYXQgdGhlIHZhcmlhYmxlICpzcXVhcmVfZmVldCogaGFzICQxOTY2MiQgbWlzc2luZyBjYXNlcywgd2hpY2ggaXMgYWJvdXQgJDk4LjE5XCUkLiBJZiB3ZSB3b3VsZCBkZWxldGVkIHRoZSBtaXNzaW5nIGNhc2VzLCB0aGUgZGF0YSBzZXQgd2lsbCBiYXJlbHkgY29udGFpbiBhbnkgZGF0YS4gTW9yZW92ZXIsIG90aGVyIG1ldGhvZHMgZm9yIGhhbmRsaW5nIG1pc3NpbmcgdmFsdWVzLCBsaWtlIHJlcGxhY2luZyBOQS12YWx1ZXMgd2l0aCB0aGUgbWVhbiBvciBtZWRpYW4sIHdvdWxkIG5vdCBiZSBhcHByb3ByaWF0ZSBhcyB0aGUgdmFyaWFibGVzIHdpbGwgYmUgYmFzZWQgb24gb25seSAkMS44MVwlJCBvZiB0aGUgZGF0YS4gVGhlcmVmb3JlLCAqc3F1YXJlX2ZlZXQqIGlzIG5vdCBpbmNsdWRlZCBpbiB0aGUgZmluYWwuIFRoZSB2YXJpYWJsZSAqaG9zdF9yZXNwb25zZV9yYXRlKiBoYXMgJDkzNDkkIG1pc3NpbmcgY2FzZXMsIHdoaWNoIGlzIGFib3V0ICQ0Ni42OVwlJC4gVGhlIHZhcmlhYmxlICpob3N0X25laWdoYm91cmhvb2QqIGhhcyAkNTk3MiQsIHdoaWNoIGlzIGFib3V0ICQyOS44MlwlJC4gVGhlIHZhcmlhYmxlICpjbGVhbmluZ19mZWUqIGhhcyAkMzYwNCQsIHdoaWNoIGlzIGFib3V0ICQxOC4wMFwlJC4gVGhlIHZhcmlhYmxlcyAgKmhvc3RfcmVzcG9uc2VfcmF0ZSosICpob3N0X25laWdoYm91cmhvb2QqIGFuZCAqY2xlYW5pbmdfZmVlKiBkbyBub3QgaGF2ZSBhcyBtYW55IG1pc3NpbmcgdmFsdWVzIGFzICpzcXVhcmVfZmVldCosIGhvd2V2ZXIsIHRoZSBzYW1lIHJlYXNvbmluZyBhcHBsaWVzLiBEdWUgdG8gdGhlc2UgZmluZGluZ3MsIHRoZXNlIHZhcmlhYmxlcyBhcmUgYWxzbyBleGNsdWRlZCBmcm9tIHRoZSBhbmFseXNlcy4gDQpgYGB7ciBNaXNzaW5nIGRhdGEgY2hlY2t9DQojIENvdW50IG1pc3NpbmcgY2FzZXMgcGVyIHZhcmlhYmxlDQpuYV9jb3VudGVyIDwtIHNhcHBseShkYXRhX3N1YiwgZnVuY3Rpb24oeCkgc3VtKGlzLm5hKHgpKSkNCnZhcnMgPC0gY29sbmFtZXMoZGF0YV9zdWIpDQoNCiMgRXh0cmFjdCBhbGwgdmFyaWFibGVzIHdpdGggTkEtdmFsdWVzDQpuYV92YWx1ZXMgPC0gdGliYmxlKHZhcmlhYmxlcyA9IHZhcnMsIG5hX2NvdW50ID0gbmFfY291bnRlcikgDQoNCiMgQ2hlY2sgbmEgY291bnQgcGVyIHZhcmlhYmxlDQpuYV92YWx1ZXMgJT4lDQogIGZpbHRlcihuYV9jb3VudCA+IDApICU+JQ0KICBhcnJhbmdlKGRlc2MobmFfY291bnQpKQ0KYGBgDQoNCk1vcmVvdmVyLCBhIGNoZWNrIGlzIHBlcmZvcm1lZCBvbiB0aGUgbnVtYmVyIG9mIGNhc2VzIHRoYXQgY29udGFpbiBtaXNzaW5nIHZhbHVlcyBpZiB0aGUgb3RoZXIgdmFsdWVzIHRoYXQgaGF2ZSBtaXNzaW5nIGNhc2VzIHdvdWxkIGJlIGluY2x1ZGVkIGluIHRoZSAnZmluYWwnIGRhdGEgc2V0LiBUaGUgdGFibGUgYmVsb3cgc2hvd3MgdGhhdCB0aGVyZSBhcmUgMjA2IGNhc2VzIHdoaWNoIGNvbnRhaW4gbWlzc2luZyB2YWx1ZXMsIHdoaWNoIGlzIGFib3V0ICQxLjAzXCUkIG9mIHRoZSBlbnRpcmUgZGF0YSBzZXQuIFNpbmNlIHRoaXMgaXMgYSB2ZXJ5IHNtYWxsIHByb3BvcnRpb24gaXQgaXMgbm90IHZlcnkgbGlrZWx5IHRoYXQgZGVsZXRpbmcgdGhlc2UgY2FzZXMgd291bGQgaGF2ZSBhIGxhcmdlIGltcGFjdCBvbiB0aGUgcHJlZGljdGlvbnMuIEZ1cnRoZXJtb3JlLCBhbGwgbW9kZWxzIHRoYXQgd2lsbCBiZSBwZXJmb3JtZWQgY2Fubm90IGhhbmRsZSBtaXNzaW5nIHZhbHVlcy4gVGhlcmVmb3JlLCB0aGUgY2FzZXMgd2l0aCBtaXNzaW5nIHZhbHVlcyBhcmUgZGVsZXRlZC4gDQpgYGB7ciBJbmNvbXBsZXRlIGNhc2VzfQ0KIyBDb21wdXRlIGluY29tcGxldGUgcm93cw0KZGF0YV9zdWIgJT4lIA0KICBzZWxlY3QoaG9zdF9zaW5jZSwgaG9zdF9yZXNwb25zZV90aW1lLCBob3N0X2xpc3RpbmdzX2NvdW50LA0KICAgICAgICAgaG9zdF9pZGVudGl0eV92ZXJpZmllZCwgYmVkcywgYmVkcm9vbXMsIGhvc3RfeWVhcnNfYWN0aXZlLCANCiAgICAgICAgIGJhdGhyb29tcykgJT4lIA0KICBjb21wbGV0ZS5jYXNlcygpICU+JSANCiAgc3VtbWFyeShjb3VudCgpKQ0KYGBgDQoNCmBgYHtyIEdlbmVyYXRlIGZpbmFsIGRhdGEgc2V0fQ0KIyBTZWxlY3QgdmFyaWFibGVzIGZvciBkYXRhIHNldA0KdmFyaWFibGVzX2FuYWx5c2lzIDwtICAgDQogIG5hX3ZhbHVlcyAlPiUgDQogIGZpbHRlcihuYV9jb3VudCA8PSAxNTgpICU+JSANCiAgc2VsZWN0KHZhcmlhYmxlcykgJT4lIA0KICBwdWxsKHZhcmlhYmxlcykNCg0KIyBDcmVhdGUgZmluYWwgZGF0YSBzZXQNCmRhdGFfc2VtaV9maW5hbCA8LSBkYXRhX3N1YiAlPiUgc2VsZWN0KGFsbF9vZih2YXJpYWJsZXNfYW5hbHlzaXMpKQ0KZGF0YV9zZW1pX2ZpbmFsIDwtIGRhdGFfc2VtaV9maW5hbCAlPiUgDQogIHNlbGVjdCgtYyhhbWVuaXRpZXMsIGFtZW5pdGllc19jbGVhbiwgaG9zdF92ZXJpZmljYXRpb25zLA0KICAgICAgICAgICAgaG9zdF92ZXJpZmljYXRpb25zX2NsZWFuLCBob3N0X3NpbmNlKSkNCmRhdGFfZmluYWwgPC0gZGF0YV9zZW1pX2ZpbmFsW2NvbXBsZXRlLmNhc2VzKGRhdGFfc2VtaV9maW5hbCksIF0NCmBgYA0KDQojIENyZWF0ZSB0cmFpbi10ZXN0IHNwbGl0DQoNCkZvciBmdXJ0aGVyIGFuYWx5c2lzIHRoZSBkYXRhIGlzIHNwbGl0IGludG8gYSB0cmFpbi10ZXN0IHNldC4NCmBgYHtyfQ0KIyBDcmVhdGUgYSB0cmFpbi1zcGxpdCBzZXRzDQpzZWVkX3ggPC0gIDEyMw0Kc2V0LnNlZWQoc2VlZF94KQ0KZGF0YV9zcGxpdCA8LSBpbml0aWFsX3NwbGl0KGRhdGFfZmluYWwsIHByb3AgPSAwLjcpDQpkYXRhX3RyYWluIDwtIHRyYWluaW5nKGRhdGFfc3BsaXQpDQpkYXRhX3Rlc3QgPC0gdGVzdGluZyhkYXRhX3NwbGl0KQ0KYGBgDQoNCiMjIEluc3BlY3RpbmcgdGhlIHByZWRpY3RlZCB2YXJpYWJsZQ0KDQpJbiBvcmRlciB0byBwcmV2ZW50IGRhdGEgbGVha2FnZXMgd2Ugb25seSBpbnNwZWN0IHRoZSBwcmVkaWN0ZWQgdmFyaWFibGUgKnByaWNlKiBpbiB0aGUgdHJhaW5pbmcgc2V0LiBJbiBvcmRlciB0byBpbnNwZWN0ICpwcmljZSogd2UgaGF2ZSBjcmVhdGVkIGEgZGlzdHJpYnV0aW9uIHBsb3QuIFRoZSBwbG90IHNob3dzIHRoYXQgdGhlIGRhdGEgc2V0IGNvbnRhaW5zIHNvbWUgb3V0bGllcnMgYW5kIHRoYXQgdGhlIGRpc3RyaWJ1dGlvbiBpcyByaWdodGx5IHNrZXdlZC4gQm90aCB0aGUgb3V0bGllcnMgYW5kIHRoZSBza2V3ZW5lc3MgbWFrZSB0aGUgZGF0YSBsZXNzIGludGVycHJldGFibGUgYW5kIHRoaXMgY291bGQgaGF2ZSBhbiBpbmZsdWVuY2Ugb24gcGVyZm9ybWFuY2Ugb2YgdGhlIG1vZGVscy4gDQpgYGB7cn0NCiMgUGxvdCBkaXN0cmlidXRpb24gcHJpY2UNCmdncGxvdChkYXRhID0gZGF0YV90cmFpbiAsIGFlcyhwcmljZSkpICsNCiAgZ2VvbV9oaXN0b2dyYW0oY29sPSJibGFjayIsDQogICAgICAgICAgICAgICAgIGJyZWFrcz1zZXEoMCwgbWF4KGRhdGFfdHJhaW4kcHJpY2UpLCBieT03NSksDQogICAgICAgICAgICAgICAgIGFlcyhmaWxsPS4uY291bnQuLikpICsNCiAgbGFicyh0aXRsZT0iRGlzdHJpYnV0aW9uIGZvciBQcmljZSIsIHg9IlByaWNlIiwgeT0iQ291bnQiKSArDQogIHNjYWxlX2ZpbGxfZ3JhZGllbnQoIkNvdW50IiwgbG93PSJncmVlbiIsIGhpZ2g9InJlZCIpICsNCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCg0KSW4gb3JkZXIgdG8gcHJldmVudCB0aGVzZSBwb3RlbnRpYWwgcHJvYmxlbXMgd2UgY3JlYXRlZCBhIG5ldyBkaXN0cmlidXRpb24gcGxvdCB3aXRoIGEgbG9nIHRyYW5zZm9ybWVkIHZhcmlhYmxlICpwcmljZSouIFRoZSBwbG90IHNob3dzIHRoYXQgdGhlIGRpc3RyaWJ1dGlvbiBpcyBsZXNzIHNrZXdlZCBhbmQgZG9lcyBub3QgY29udGFpbiBtYW55IGxhcmdlIG91dGxpZXJzLiBDb25zZXF1ZW50bHksIHRoZSBkYXRhIGlzIG1vcmUgaW50ZXJwcmV0YWJsZS4gVGhlcmVmb3JlLCB3ZSB3aWxsIHVzZSB0aGUgbG9nIHRyYW5zZm9ybWVkICpwcmljZSogZm9yIG91ciBtb2RlbHMuIA0KYGBge3J9DQojIFBsb3QgZGlzdHJpYnV0aW9uIHByaWNlDQpnZ3Bsb3QoZGF0YSA9IGRhdGFfdHJhaW4gLCBhZXMobG9nKHByaWNlICsgMSkpKSArDQogIGdlb21faGlzdG9ncmFtKGNvbD0iYmxhY2siLA0KICAgICAgICAgICAgICAgICBhZXMoZmlsbD0uLmNvdW50Li4pKSArDQogIGxhYnModGl0bGU9IkRpc3RyaWJ1dGlvbiBmb3IgTG4gUHJpY2UiLCB4PSJMbiBQcmljZSIsIHk9IkNvdW50IikgKw0KICBzY2FsZV9maWxsX2dyYWRpZW50KCJDb3VudCIsIGxvdz0iZ3JlZW4iLCBoaWdoPSJyZWQiKSArDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQoNCmBgYHtyfQ0KIyBMb2cgdHJhbnNmb3JtIHRoZSBwcmljZSBpbiBmb3IgYm90aCB0cmFpbmluZyBhbmQgdGVzdCBzZXQNCmRhdGFfZmluYWwkcHJpY2UgPC0gbG9nKGRhdGFfZmluYWwkcHJpY2UgKyAxKQ0KDQojIFJlc3BsaXQgdGhlIGRhdGEgdXNpbmcgdGhlIHNhbWUgc2VlZCANCnNldC5zZWVkKHNlZWRfeCkNCmRhdGFfc3BsaXQgPC0gaW5pdGlhbF9zcGxpdChkYXRhX2ZpbmFsLCBwcm9wID0gMC43KQ0KZGF0YV90cmFpbiA8LSB0cmFpbmluZyhkYXRhX3NwbGl0KQ0KZGF0YV90ZXN0IDwtIHRlc3RpbmcoZGF0YV9zcGxpdCkNCg0KYGBgDQoNCg0KIyMgSy1mb2xkIGNyb3NzIHZhbGlkYXRpb24gDQoNCk1vcmVvdmVyLCB3ZSBoYXZlIGdlbmVyYXRlZCAxMC1mb2xkIGNyb3NzIHZhbGlkYXRpb24gc2V0cy4NCmBgYHtyfQ0KIyBHZW5lcmF0ZSAxMC1mb2xkIENWIHNldHMNCnNldC5zZWVkKDMyMSkNCmRhdGFfZm9sZHMgPC0gdmZvbGRfY3YoZGF0YV90cmFpbiwgdiA9IDEwKQ0KZGF0YV9mb2xkcw0KYGBgDQoNCiMjIFJlbW92ZSBkYXRhIGZyYW1lcyB0byBhdm9pZCBsZWFrYWdlcyBhbmQgZXJyb3JzDQpgYGB7cn0NCnJtKGRhdGEpDQpybShkYXRhX3N1YikNCnJtKGRhdGFfc2VtaV9maW5hbCkNCnJtKG5hX3ZhbHVlcykNCmBgYA0KDQojIFBhcnQgMjogTW9kZWxsaW5nIEFwcHJvYWNoZXMNCg0KIyBMaW5lYXIgTGFzc28gUmVndWxhcml6ZWQgUmVncmVzc2lvbiBNb2RlbA0KDQpJbiB0aGlzIHNlY3Rpb24sIGEgcmVndWxhcml6ZWQgcmVncmVzc2lvbiBtb2RlbCB3aWxsIGJlIHNwZWNpZmllZCBhbmQgdHJhaW5lZC4gQSBsYXNzbyBwZW5hbHR5IGlzIGNob3NlbiB0byBzaW11bHRhbmVvdXNseSBwZXJmb3JtIHN1YnNldCBzZWxlY3Rpb24uIFRoZXJlZm9yZSwgYSBtaXh0dXJlIGlzIHNldCB0byAxIGluIHRoZSBtb2RlbCBzcGVjaWZpY2F0aW9uLiANCg0KIyMgTW9kZWwgc3BlY2lmaWNhdGlvbg0KDQpTcGVjaWZpY2F0aW9uIG9mIGxhc3NvLXJlZ3VsYXJpemVkIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwsIHdoZXJlIHRoZSBwZW5hbHR5IHBhcmFtZXRlciB3aWxsIGJlIHR1bmVkOg0KYGBge3IgcmVzdWx0cz0naGlkZSd9DQojIFNwZWNpZnkgdGhlIG1vZGVsIGFuZCBlbmdpbmUgdXNlZA0KbGFzc29fbGlucmVnIDwtIGxpbmVhcl9yZWcocGVuYWx0eSA9IHR1bmUoKSwgbWl4dHVyZSA9IDEpICU+JSANCiAgc2V0X2VuZ2luZSgiZ2xtbmV0IikNCg0KIyBDaGVjayB0aGF0IG1vZGVsIHNwZWNpZmllZCBjb3JyZWN0bHk6DQpsYXNzb19saW5yZWcgJT4lIHRyYW5zbGF0ZSgpDQpgYGANCg0KIyMgUHJlcHJvY2Vzc2luZyByZWNpcGUNCg0KSW4gdGhpcyBzZWN0aW9uLCB0aGUgcmVjaXBlIGlzIGZvcm11bGF0ZWQuIEFsbCB0aGUgZmluYWwgZGF0YXNldCB2YXJpYWJsZXMgYXJlIGluY2x1ZGVkIGluIHRoZSByZWNpcGUsIGluIG9yZGVyIHRvIHBlcmZvcm0gdGhlIHN1YnNldCBzZWxlY3Rpb24gYnkgbWVhbnMgb2YgYSBsYXNzbyBwZW5hbHR5LiBBcyB0aGUgcHJvcGVydHkgdHlwZSBhbmQgYmVkIHR5cGUgaGF2ZSBzb21lIGNhdGVnb3JpZXMgd2l0aCBqdXN0IGEgZmV3IG9ic2VydmF0aW9ucywgdGhlIGNhdGVnb3JpZXMgdGhhdCBpbmNsdWRlIGxlc3MgdGhhbiAxJSBvZiB0aGUgdG90YWwgbnVtYmVyIG9mIG9ic2VydmF0aW9ucyBhcmUgY29tYmluZWQgdG8gIm90aGVyIiBjYXRlZ29yeSB0byBhdm9pZCBzcGFyc2UgZGF0YS4gQWRkaXRpb25hbGx5LCBkdW1taWVzIGFyZSBjcmVhdGVkIGZvciBhbGwgb2YgdGhlIG5vbWluYWwgdmFyaWFibGVzLiBMYXN0bHksIGFsbCB0aGUgdmFyaWFibGVzIGFyZSBub3JtYWxpemVkLg0KYGBge3IgcmVzdWx0cz0naGlkZSd9DQojIFByZXBhcmUgdGhlIHJlY2lwZSBieSBzZXR0aW5nIHVwIHRoZSByZWdyZXNzaW9uIG1vZGVsLCBzZXR0aW5nIGlkIGFzIGlkIHZhcmlhYmxlLCBjb21iaW5pbmcgc21hbGwgY2F0ZWdvcmllcyB0byBvdGhlciBjbGFzcywgYW5kIGNyZWF0aW5nIGR1bW1pZXMgYW5kIG5vcm1hbGl6aW5nIHZhcmlhYmxlcw0KbGFzc29fcmVjaXBlIDwtICByZWNpcGUocHJpY2UgfiAuLCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgZGF0YSA9IGRhdGFfdHJhaW4pICU+JSANCiAgICAgICAgICAgICAgICAgICAgICAgIHVwZGF0ZV9yb2xlKGlkLCBuZXdfcm9sZSA9ICJJRCIpICU+JQ0KICAgICAgICAgICAgICAgICAgICAgICAgc3RlcF9vdGhlcihwcm9wZXJ0eV90eXBlLCBiZWRfdHlwZSwgIHRocmVzaG9sZCA9IDAuMDEsIG90aGVyID0gIm90aGVyIHZhbHVlcyIpICU+JSANCiAgICAgICAgICAgICAgICAgICAgICAgIHN0ZXBfZHVtbXkoYWxsX25vbWluYWwoKSwgLWFsbF9vdXRjb21lcygpKSAlPiUNCiAgICAgICAgICAgICAgICAgICAgICAgIHN0ZXBfbm9ybWFsaXplKGFsbF9wcmVkaWN0b3JzKCksIC1hbGxfb3V0Y29tZXMoKSkNCmxhc3NvX3JlY2lwZQ0KYGBgDQoNClRlc3RpbmcgdGhhdCB0aGlzIHdvcmtzIHByb3Blcmx5Og0KYGBge3J9DQojIFByZXBhcmUgYW5kIGJha2UgdGhlIGRhdGEgKG9uIHRyYWluaW5nIHNldCkgdG8gY2hlY2sgdGhhdCB0aGUgcmVjaXBlIHByZXBhcmVzIHRoZSBkYXRhIGNvcnJlY3RseQ0KZGF0YV9iYWtlZCA8LSBsYXNzb19yZWNpcGUgJT4lIHByZXAoZGF0YV90cmFpbikgJT4lIGJha2UoZGF0YV90cmFpbikNCmhlYWQoZGF0YV9iYWtlZCkNCmBgYA0KDQojIyBDcmVhdGUgTGFzc28gV29ya2Zsb3cNCmBgYHtyIHJlc3VsdHM9J2hpZGUnfQ0KIyBDb21iaW5lIHRoZSBtb2RlbCBzcGVjaWZpY2F0aW9uIGFuZCByZWNpcGxlIHRvIGEgd29ya2Zsb3cNCmxhc3NvX3dmIDwtIHdvcmtmbG93KCkgJT4lIA0KICBhZGRfcmVjaXBlKGxhc3NvX3JlY2lwZSkgJT4lIA0KICBhZGRfbW9kZWwobGFzc29fbGlucmVnKQ0KbGFzc29fd2YNCmBgYA0KDQojIyBUdW5pbmcgZ3JpZHMNCk5leHQsIHRoZSAkXGxhbWJkYSQgcGFyYW1ldGVyIG9mIHRoZSBsYXNzbyBtb2RlbCB3aWxsIGJlIHR1bmVkLiBGb3IgdGhhdCBwdXJwb3NlLCBhIHR1bmluZyBncmlkIGlzIHNwZWNpZmllZC4gDQpgYGB7cn0NCiMgU2V0IHR1bmluZyBncmlkDQpncmlkX2xhc3NvIDwtIHRpYmJsZShwZW5hbHR5ID0gMTBeKHNlcShmcm9tID0gLTUsIHRvID0gMSwgbGVuZ3RoLm91dCA9IDcwKSkpDQpgYGANCg0KIyMgVHVuaW5nIGxhc3NvLXBlbmFsaXplZCBsaW5lYXIgcmVncmVzc2lvbg0KMTAtay1jcm9zcy12YWxpZGF0aW9uIGlzIHVzZWQgdG8gdHVuZSB0aGUgbGFzc28tcGVuYWxpemVkIGxpbmVhciByZWdyZXNzaW9uLCBhbmQgdGhlIG1ldHJpY3MgYXJlIHBsb3R0ZWQgYWdhaW5zdCB0aGUgZGlmZmVyZW50IHZhbHVlcyBvZiAkXGxhbWJkYSQuDQpgYGB7cn0NCiAjIFBlcmZvcm0gZ3JpZCBzZWFyY2ggb3ZlciB0aGUgdHVuaW5nIGdyaWQgb2YgcGVuYWx0eSB2YWx1ZXMNCiBsYXNzb190dW5lIDwtIGxhc3NvX3dmICU+JSANCiAgdHVuZV9ncmlkKHJlc2FtcGxlcyA9IGRhdGFfZm9sZHMsIA0KICAgICAgICAgICAgZ3JpZCA9IGdyaWRfbGFzc28sDQogICAgICAgICAgICBtZXRyaWNzID0gbWV0cmljX3NldChtYWUsIHJtc2UsIHJzcV90cmFkKSkNCmBgYA0KDQpgYGB7ciBtZXNzYWdlPVRSVUV9DQojIFN0b3JlIG1ldHJpY3MgaW4gdmFyaWFibGUNCmxhc3NvX3R1bmVfbWV0cmljcyA8LSBsYXNzb190dW5lICU+JSANCiAgY29sbGVjdF9tZXRyaWNzKCkNCg0KIyBQbG90IGFsbCByZXN1bHRzIG1ldHJpY3MgDQpsYXNzb190dW5lX21ldHJpY3MgJT4lDQogIGdncGxvdChhZXMoeCA9IHBlbmFsdHksIHkgPSBtZWFuLCANCiAgICAgICAgICAgICB5bWluID0gbWVhbiAtIHN0ZF9lcnIsIHltYXggPSBtZWFuICsgc3RkX2VycikpICsgDQogIGdlb21fbGluZXJhbmdlKGFscGhhID0gMC41LCBjb2xvdXIgPSAicmVkIikgKyANCiAgZ2VvbV9wb2ludChjb2xvdXIgPSAicmVkIikgKyANCiAgIGZhY2V0X3dyYXAofiAubWV0cmljLCBzY2FsZSA9ICJmcmVlX3kiKSArDQogIHNjYWxlX3hfbG9nMTAoKSArIA0KICBsYWJzKHkgPSAiTGFzc28gUGVyZm9ybWFuY2UgTWV0cmljcyIsIHggPSBleHByZXNzaW9uKGxhbWJkYSkpDQoNCiMgUGxvdCBNQUUgDQpsYXNzb190dW5lX21ldHJpY3MgJT4lIGZpbHRlcigubWV0cmljID09ICJtYWUiKSAlPiUgDQogIGdncGxvdChhZXMoeCA9IHBlbmFsdHksIHkgPSBtZWFuLCANCiAgICAgICAgICAgICB5bWluID0gbWVhbiAtIHN0ZF9lcnIsIHltYXggPSBtZWFuICsgc3RkX2VycikpICsgDQogIGdlb21fbGluZXJhbmdlKGFscGhhID0gMC41LCBjb2xvdXIgPSAicmVkIikgKyANCiAgZ2VvbV9wb2ludChjb2xvdXIgPSAicmVkIikgKyANCiAgc2NhbGVfeF9sb2cxMCgpICsgDQogIGxhYnMoeSA9ICJtYWUiLCB4ID0gZXhwcmVzc2lvbihsYW1iZGEpLCANCiAgICAgICB0aXRsZSA9ICJMYXNzbyBSZWdyZXNzc2lvbiBNQUUiKSArDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQ0KYGBgDQoNCk5leHQsIHRoZSBMYW1iZGEgdmFsdWUgd2hpY2ggcmVzdWx0cyBpbiBiZXN0IG1vZGVsIHBlcmZvcm1hbmNlIG9uIHRoZSB0cmFpbiBzZXQgaXMgc2VsZWN0ZWQuIEl0IGNhbiBiZSBzZWVuIHRoYXQgYXMgdGhlIFJNU0UgaXMgbW9yZSBzZW5zaXRpdmUgZm9yIGxhcmdlIHJlc2lkdWFscywgdGhlIHN0YW5kYXJkIGVycm9ycyBvZiB0aGVzZSBtZXRyaWNzIGFyZSBsYXJnZXIgY29tcGFyZWQgdG8gdGhlIHN0YW5kYXJkIGVycm9ycyBvZiBtZWFuIGFic29sdXRlIGVycm9yIChNQUUpLiBUaGVyZWZvcmUsIHRoZSBtZWFuIGFic29sdXRlIGVycm9yIGlzIHVzZWQgdG8gc2VsZWN0IHRoZSBiZXN0IG1vZGVsLiANCmBgYHtyfQ0KIyBTaG93IGJlc3QgbW9kZWxzIHdpdGggY29ycmVzcG9uZGluZyBwZW5hbHR5IHZhbHVlcw0KbGFzc29fdHVuZSAlPiUgc2hvd19iZXN0KCJtYWUiKQ0KYGBgDQoNClRoZSBiZXN0IG1vZGVsIGlzIHNlbGVjdGVkIHVzaW5nIHRoZSBvbmUgc3RhbmRhcmQgZXJyb3IgcnVsZSwgd2hlcmUgdGhlIHNpbXBsZXN0IG1vZGVsIHRoYXQgaGFzIE1BRSBpbnNpZGUgb25lIHN0YW5kYXJkIGVycm9yIGZyb20gdGhlIGFic29sdXRlIGJlc3QgbW9kZWwgaXMgY2hvc2VuIHRvIGF2b2lkIG92ZXJmaXR0aW5nLg0KYGBge3J9DQojIFNlbGVjdCBiZXN0IG1vZGVsIGFjY29yZGluZyB0byAxIHN0ZCBlcnJvciBydWxlDQpsYXNzb18xc2VfbW9kZWwgPC0gc2VsZWN0X2J5X29uZV9zdGRfZXJyKGxhc3NvX3R1bmUsIG1ldHJpYyA9ICJtYWUiLCBkZXNjKHBlbmFsdHkpKQ0KbGFzc29fMXNlX21vZGVsDQpgYGANCg0KQXMgY2FuIGJlIHNlZW4sIHRoZSBiZXN0IG1vZGVsIGhhcyBhIHBlbmFsdHkgcGFyYW1ldGVyIG9mIDAuMDA3Lg0KDQpGaW5hbGl6ZSB0aGUgd29ya2Zsb3c6DQpgYGB7ciwgcmVzdWx0cz0naGlkZSd9DQojIEZpbmFsaXplIGxhc3NvIHdmIHdpdGggdGhlIHNlbGVjdGVkIGJlc3QgbW9kZWwNCmxhc3NvX3dmX3R1bmVkIDwtIA0KICBsYXNzb193ZiAlPiUgDQogIGZpbmFsaXplX3dvcmtmbG93KGxhc3NvXzFzZV9tb2RlbCkNCmxhc3NvX3dmX3R1bmVkDQpgYGANCg0KYGBge3J9DQojIFRyYWluIHRoZSB0dW5lZCBtb2RlbCBvbiBhbGwgb2YgdGhlIHRyYWluIGRhdGEgYW5kIHRlc3Qgb24gdGhlIHRlc3QgZGF0YSANCmxhc3NvX2xhc3RfZml0IDwtIGxhc3NvX3dmX3R1bmVkICU+JSANCiAgbGFzdF9maXQoZGF0YV9zcGxpdCwgbWV0cmljcyA9IG1ldHJpY19zZXQobWFlLCBybXNlLCByc3FfdHJhZCkpDQpgYGANCg0KVGhlIHBlcmZvcm1hbmNlIG9uIHRoZSB0ZXN0IHNldCBmb3IgdGhpcyBtb2RlbCBpczoNCmBgYHtyfQ0KIyBDb2xsZWN0IG1ldHJpY3MgZnJvbSB0aGUgbW9kZWwgb24gdGhlIHRlc3Qgc2V0DQpsYXNzb190ZXN0X21ldHJpY3MgPC0gbGFzc29fbGFzdF9maXQgJT4lIGNvbGxlY3RfbWV0cmljcygpDQpsYXNzb190ZXN0X21ldHJpY3MNCmBgYA0KQXMgc2VlbiBhYm92ZSwgdGhlIGZpbmFsIGxhc3NvIG1vZGVsIGhhcyBtZWFuIGFic29sdXRlIGVycm9yIG9mIDAuMjcsIHJvb3QgbWVhbiBzcXVhcmVkIGVycm9yIG9mIDAuMzcgYW5kIFIgc3F1YXJlZCBvbiA0OCw3JSBvbiB0aGUgdGVzdCBkYXRhLg0KDQpUbyBhc3Nlc3MgdGhlIGltcG9ydGFuY2Ugb2YgdGhlIHByZWRpY3RvciB2YXJpYWJsZXMsIG1vZGVsIHBhcmFtZXRlciBlc3RpbWF0ZXMgYXJlIGNhbGN1bGF0ZWQgYmVsb3c6DQpgYGB7cn0NCiMgRml0IHRoZSBtb2RlbCBvbiB0aGUgdHJhaW5pbmcgZGF0YSBhbmQgcHVsbCB0aGUgbW9kZWwgY29lZmZpY2llbnRzIGZvciB0aGUgdmFyaWFibGVzDQpsYXNzb193Zl90dW5lZCAlPiUgZml0KGRhdGFfdHJhaW4pICU+JSBwdWxsX3dvcmtmbG93X2ZpdCgpICU+JSB0aWR5KCkgDQpgYGANCg0KQXMgbGFzc28gcGVyZm9ybXMgc3Vic2V0IHNlbGVjdGlvbiBhdXRvbWF0aWNhbGx5LCBzb21lIHZhcmlhYmxlcyBoYXZlIGEgY29lZmZpY2llbnQgb2YgemVyby4gVGhlcmUgYXJlIG11bHRpcGxlIHZhcmlhYmxlcyB3aXRoIGNvZWZmaWNpZW50IG9mIHplcm8sIHdoaWNoIGltcGxpZXMgdGhhdCB0aGVzZSB2YXJpYWJsZXMgYXJlIGxlc3MgaW1wb3J0YW50IGZvciB0aGUgcHJpY2UgcHJlZGljdGlvbiBvZiBuZXcgQWlyYm5iIGxpc3RpbmdzLiBUaGUgbW9zdCBpbXBvcnRhbnQgdmFyaWFibGVzIGNhbiBiZSBpZGVudGlmaWVkIGJ5IGxvb2tpbmcgYXQgdGhlIGNvZWZmaWNpZW50cyBhcyB3ZWxsLCBhbmQgdGhlIDQgbW9zdCBpbXBvcnRhbnQgdmFyaWFibGVzIGFyZSBudW1iZXIgb2YgYWNjb21tb2RhdGVzLCB0aGUgbnVtYmVyIG9mIGRheXMgdGhhdCB0aGUgYWlyYm5iIGlzIGF2YWlsYWJsZSBpbnNpZGUgMzAgZGF5cywgcm9vbSB0eXBlIG9mIGVudGlyZSBob21lIGFwYXJ0bWVudCwgYW5kIGxhc3RseSwgQ2VudHJ1bS1XZXN0IG5laWdoYm91cmhvb2QuDQoNCiMgUmFuZG9tIEZvcmVzdA0KDQojIyBSYW5kb20gZm9yZXN0IHNwZWNpZmljYXRpb24gDQoNCiMjIyBSZWNpcGUNCldpdGhpbiB0aGlzIHNlY3Rpb24sIGEgcmFuZG9tIGZvcmVzdCB3aWxsIGJlIGNyZWF0ZWQuIEZpcnN0IGEgcHJlcHJvY2Vzc2luZyByZWNpcGUgaXMgY3JlYXRlZC4gDQpUaGUgaWQgdmFyaWFibGUgaXMgdXBkYXRlZCB0byBhIHNlcGVyYXRlIHJvbGUsIGluc3RlYWQgb2YgYmVpbmcgYSBwcmVkaWN0b3IuIA0KYGBge3IgUmVjaXBlfQ0KIyBTcGVjaWZ5IHJlY2lwZQ0KcmZfcmVjaXBlIDwtIHJlY2lwZShwcmljZSB+IC4sIGRhdGEgPSBkYXRhX3RyYWluKSAlPiUNCiAgdXBkYXRlX3JvbGUoaWQsIG5ld19yb2xlID0gImlkIHZhciIpDQoNCnJmX3JlY2lwZQ0KYGBgDQoNCiMjIyBUdW5lIHNwZWNpZmljYXRpb25zDQoNCldpdGhpbiB0aGlzIHNlY3Rpb24gdGhlIHR1bmUgc3BlY2lmaWNhdGlvbiBhcmUgbWVudGlvbmVkLiBUaGUgKm10cnkqIGlzIHRoZSBudW1iZXIgb2YgZmVhdHVyZXMgdGhhdCBhcmUgdXNlZCBhdCBlYWNoIHNwbGl0LiBUaGUgZXhhY3QgbXRyeSB2YWx1ZSB3aWxsIGJlIHR1bmVkIGxhdGVyIG9uLiBEaWZmZXJlbnQgdmFsdWVzIGZvciB0cmVlcyB3aGVyZSB0ZXN0ZWQgKDIwMCwgNTAwICYgMTAwMCkuIEluY3JlYXNpbmcgdGhlIGFtb3VudCBvZiB0cmVlcyBkaWQgbm90IGhhdmUgbXVjaCBpbXBhY3Qgb24gdGhlIHJlc3VsdHMuIFRoZXJlZm9yZSwgYSB0cmVlIHNpemUgb2YgMjAwIGlzIGNob3NlbiB0byBzYXZlIGNvbXB1dGF0aW9uYWwgdGltZS4gDQpgYGB7ciBtZXNzYWdlPUZBTFNFfQ0KIyBUdW5lIHNwZWNpZmljYXRpb24NCnJmX3R1bmVfc3BlYyA8LSByYW5kX2ZvcmVzdChtdHJ5ID0gdHVuZSgpLCB0cmVlcyA9IDIwMCkgJT4lDQogIHNldF9lbmdpbmUoInJhbmdlciIpICU+JQ0KICBzZXRfbW9kZSgicmVncmVzc2lvbiIpDQpgYGANCg0KVGhlIHJlY2lwZSBhbmQgdGhlIG1vZGVsIGFyZSBjb21iaW5lZCBpbnRvIGEgd29ya2Zsb3cgdGhhdCBjYW4gYmUgdHVuZWQuDQpgYGB7ciBtZXNzYWdlPUZBTFNFfQ0KIyBXb3JrZmxvdyBjcmVhdGlvbg0KcmZfdHVuZV93ZiA8LSB3b3JrZmxvdygpICU+JQ0KICBhZGRfcmVjaXBlKHJmX3JlY2lwZSkgJT4lDQogIGFkZF9tb2RlbChyZl90dW5lX3NwZWMpDQpgYGANCg0KQSBtZXRyaWMgc2V0IGlzIHNwZWNpZmllZCwgd2hpY2ggY2FsY3VsYXRlcyB0aGUgKlJvb3QgTWVhbiBTcXVhcmUgRXJyb3IgKFJNU0UpKiwgKnRoZSBNZWFuIEFic29sdXRlIEVycm9yIChNQUUpKiBhbmQgdGhlICpSLXNxdWFyZWQgKHJzcV90cmFkKSogaXMgY3JlYXRlZC4gDQpgYGB7ciBDbGFzcyBtZXRyaWNzfQ0KIyBDbGFzcyBtZXRyaWNzIHNwZWNpZmljYXRpb24gDQpjbGFzc19tZXRyaWNzIDwtIG1ldHJpY19zZXQocm1zZSwgbWFlLCByc3FfdHJhZCkNCmBgYA0KDQpUaGUgY29tbWFuZCBiZWxsb3cgYWxsb3dzIHVzIHRvIGRvIGNvbXB1dGF0aW9ucyBpbiBwYXJhbGxlbC4NCmBgYHtyIG1lc3NhZ2U9RkFMU0V9DQpyZWdpc3RlckRvUGFyYWxsZWwoKQ0KYGBgDQoNClRoZSBjb21tYW5kIGdyaWQgPSB0aWJibGUobXRyeSA9IDE6MzMpIHdhcyB1dGxpc2VkLCBhcyB0aGlzIGFsbG93cyB0aGUgcmFuZG9tIGZvcmVzdCB0byBjb25zaWRlciBhbGwgbnVtYmVyIG9mIHZhcmlhYmxlcyBhdCBlYWNoIHNwbGl0LiBCYXNlZCBvbiB0aGUgTUFFIGNyaXRlcmlhLCBhIG10cnkgb2YgNSwgNiwgNywgOCAmIDkgd2FzIGZvdW5kIGFzIHRoZSBvcHRpbWFsIHNvbHV0aW9uLiBBZnRlcndhcmRzLCBhIG10cnkgb2YgYygxOjEwKSkgaXMgdGFrZW4gdGhhdCB3aWxsIGluY2x1ZGUgdGhlIG9wdGltYWwgdmFsdWVzLCBhcyB3ZWxsIG10cnkgdmFsdWVzIG9mIDEgdXAgdW50aWwgNCBhbmQgYSBtdHJ5IG9mIDEwLiBUaGlzIGFsbG93cyB1cyB0byBzZWUgdGhhdCB0aGUgbXRyeSBpcyBpbml0aWFsbHkgaW5jcmVhc2VkIHVwIHVudGlsIGl0IHJlYWNoZXMgaXRzIG9wdGltYWwgbXRyeSBzb2x1dGlvbi4gIA0KYGBge3IgbWVzc2FnZT1GQUxTRX0NCiMgRGVmaW5lIHRoZSB0dW5lIGdyaWQgDQpyZl90dW5lZ3JpZCA8LSB0aWJibGUobXRyeSA9IGMoMToxMCkpDQpgYGANCg0KYGBge3IgR3JpZH0NCiMgVHVuZSB0aGUgZ3JpZA0Kc2V0LnNlZWQoMTIzNDUpDQpyZl90dW5lX3JlcyA8LSB0dW5lX2dyaWQoDQogIHJmX3R1bmVfd2YsDQogIHJlc2FtcGxlcyA9IGRhdGFfZm9sZHMsDQogIGdyaWQgPSByZl90dW5lZ3JpZCwNCiAgbWV0cmljcyA9IGNsYXNzX21ldHJpY3MNCikNCnJmX3R1bmVfcmVzDQpgYGANCg0KIyMgU2VsZWN0aW5nIHR1bmluZyBwYXJhbWV0ZXJzIA0KYGBge3IgQ29sbGVjdCBtZXRyaWNzfQ0KIyBDb2xsZWN0IG1ldHJpY3MNCnJmX3R1bmVfcmVzICU+JQ0KICBjb2xsZWN0X21ldHJpY3MoKQ0KYGBgDQoNClRoaXMgcGxvdCBpbGx1c3RyYXRlcyB0aGUgYmVzdCBtdHJ5LCBiYXNlZCBvbiB0aGUgY3JpdGVyaWEgb2YgdGhlIE1BRS4gQSBsb3dlciBNQUUgd291bGQgaW5kaWNhdGUgYSBiZXR0ZXIgcmVzdWx0LCBhcyBhIGxvd2VyIHZhbHVlIGluZGljYXRlcyBhIGxvd2VyIGVycm9yIG9mIHByZWRpY3Rpb24uIA0KYGBge3IgUGxvdCBNQUV9DQojIFBsb3QgcmVzdWx0cyBhbGwgbWV0cmljcw0KcmZfdHVuZV9yZXMgJT4lDQogIGNvbGxlY3RfbWV0cmljcygpICU+JQ0KICBmaWx0ZXIoLm1ldHJpYyAlaW4lIGMoInJtc2UiLCAibWFlIiwgInJzcV90cmFkIikpICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBtdHJ5LCB5ID0gbWVhbiwgeW1pbiA9IG1lYW4gLSBzdGRfZXJyLCB5bWF4ID0gbWVhbiArIHN0ZF9lcnIsIA0KICAgICAgICAgICAgIGNvbG91ciA9IC5tZXRyaWMpKSArDQogIGdlb21fZXJyb3JiYXIoKSArIA0KICBnZW9tX2xpbmUoKSArDQogIGdlb21fcG9pbnQoKSArDQogIGZhY2V0X2dyaWQoLm1ldHJpYyB+IC4sIHNjYWxlcyA9ICJmcmVlX3kiKSArDQogIGxhYnModGl0bGUgPSAiUmFuZG9tIEZvcmVzdCBwZXJmb3JtYW5jZSBtZXRyaWNzIikgKw0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkNCmBgYA0KDQpgYGB7cn0NCiMgUGxvdCB0aGUgTUFFIGJhc2VkDQpyZl90dW5lX3JlcyAlPiUNCiAgY29sbGVjdF9tZXRyaWNzKCkgJT4lDQogIGZpbHRlcigubWV0cmljID09ICJtYWUiKSAlPiUgDQogIGdncGxvdChhZXMoeCA9IG10cnksIHkgPSBtZWFuLCB5bWluID0gbWVhbiAtIHN0ZF9lcnIsIHltYXggPSBtZWFuICsgc3RkX2VycikpICsNCiAgZ2VvbV9lcnJvcmJhcihjb2xvdXIgPSAicmVkIikgKyANCiAgZ2VvbV9saW5lKGNvbG91ciA9ICJyZWQiKSArDQogIGdlb21fcG9pbnQoY29sb3VyID0gInJlZCIpICsNCiAgbGFicyh5ID0gIm1hZSIsIHRpdGxlID0gIlJhbmRvbSBGb3Jlc3QgcGVyZm9ybWFuY2UgbWV0cmljcyIpICsNCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpDQpgYGANCg0KVGhpcyBjb21tYW5kIHdpbGwgc2hvdyB0aGUgYmVzdCBtdHJ5IGJhc2VkIG9uIHRoZSBNQUUgbWV0cmljcy4gDQpgYGB7ciBCZXN0IE1BRX0NCiMgRmluZCB0aGUgbXRyeSB3aXRoIHRoZSBiZXN0IE1BRQ0KcmZfdHVuZV9yZXMgJT4lIHNob3dfYmVzdCgibWFlIikNCmBgYA0KDQojIyBCZXN0IG1vZGVsIHNlbGVjdGlvbg0KDQpUaGUgYmVzdCBtb2RlbCBiYXNlZCBvbiB0aGUgTUFFIGNyaXRlcmlhIGlzIHNlbGVjdGVkIGFuZCBldmVudHVhbGx5IGZpbmFsaXplZCBpbnRvIHRoZSB3b3JrZmxvdy4gDQpgYGB7ciBCZXN0IG1vZGVsfQ0KIyBCZXN0IG1vZGVsIHNlbGVjdGlvbg0KYmVzdF9ybXNlIDwtIHNlbGVjdF9iZXN0KHJmX3R1bmVfcmVzLCAibWFlIikNCmZpbmFsX3JmIDwtIGZpbmFsaXplX3dvcmtmbG93KHJmX3R1bmVfd2YsIGJlc3Rfcm1zZSkNCmZpbmFsX3JmDQpgYGANCg0KIyMjIFRlc3Qgc2V0IHBlcmZvcm1hbmNlDQoNCk5vdyB3ZSBjYW4gdHJhaW4gdGhlIGZpbmFsaXplZCB3b3JrZmxvdyBvbiBvdXIgZW50aXJlIHRyYWluaW5nIHNldA0KYGBge3IgRmluYWxpc2V9DQojIEZpbmFsaXplIHdvcmtmbG93IG9uIHRyYWluaW5nIHNldA0KZmluYWxfcmVzIDwtIGZpbmFsX3JmICU+JQ0KICBsYXN0X2ZpdChkYXRhX3NwbGl0LCBtZXRyaWNzID0gY2xhc3NfbWV0cmljcykNCmBgYA0KDQpUaGUgcmVzdWx0cyBiYXNlZCBvbiB0aGUgdGVzdCBzZXQgd2lsbCBiZSANCmBgYHtyIFRlc3QgcmVzdWx0c30NCiMgU2NvcmUgb24gdGVzdCBkYXRhDQpzZXQuc2VlZCg1NDMyMSkNCmZpbmFsX3JlcyAlPiUNCiAgY29sbGVjdF9tZXRyaWNzKCkNCmBgYA0KDQojIyMgVmFyaWFibGUgaW1wb3J0YW5jZSANCg0KTm93IHdlIHRyeSB0byBhc3NlcyB0aGUgdmFyaWFibGUgaW1wb3J0YW5jZS4gV2Ugd2lsbCByZWZpdCB0aGUgbW9kZWwgYmFzZWQgb24gb3VyIHByZXZpb3VzIHR1bmUgcGFyYW1ldGVycy4gV2UgcHJldmlvdXN5bHkgZm91bmQgYW4gb3B0aW1hbCBtdHJ5IG9mIDcsIHRoYXQncyB3aHkgdGhlIG10cnkgaXMgc3BlY2lmaWVkIGFzIDcuIEhvd2V2ZXIsIGRvIGtlZXAgaW4gbWluZCB0aGF0IGJlY2F1c2Ugb2YgdGhlIHJhbmRvbSBlbGVtZW50IHdpdGhpbiBhIHJhbmRvbSBmb3Jlc3QsIHRoYXQgdGhpcyBpbml0aWFsIHZhbHVlIG1pZ2h0IGFsdGVyLiBXZSBub3RpY2VkIHRoYXQgdGhlIG9wdGltYWwgbXRyeSBzd2l0Y2hlcyBiZXR3ZWVuIDYsIDcgJiA4LiANCmBgYHtyIFJlZml0fQ0KIyBSZWZpdCB0aGUgbW9kZWwNCnJmX21vZGVsX3ZpIDwtIHJhbmRfZm9yZXN0KG10cnkgPSA3LCB0cmVlcyA9IDIwMCkgJT4lDQogIHNldF9lbmdpbmUoInJhbmdlciIsIGltcG9ydGFuY2UgPSAicGVybXV0YXRpb24iKQ0KDQpyZl92aV93ZiA8LSB3b3JrZmxvdygpICU+JSANCiAgYWRkX21vZGVsKHJmX21vZGVsX3ZpKSAlPiUgDQogIGFkZF9yZWNpcGUocmZfcmVjaXBlKQ0KDQojIEZpdCB0aGUgbW9kZWwgYWdhaW4NCnNldC5zZWVkKDEyMzQ1KQ0KcmZfdmlfZml0IDwtIHJmX3ZpX3dmICU+JSBmaXQoZGF0YSA9IGRhdGFfdHJhaW4pDQpgYGANCg0KV2UgY2FuIHVzZSB0aGUgcmVmaXR0ZWQgbW9kZWwgaW4gb3JkZXIgdGhlIGdhdGhlciB0aGUgdmFyaWFibGUgaW1wb3J0YW5jZSANCmBgYHtyIFZhcmlhYmxlIGltcG9ydGFuY2V9DQojIFZhcmlhYmxlIGltcG9ydGFuY2UgDQpyZl92aV9maXQgJT4lIHB1bGxfd29ya2Zsb3dfZml0KCkgJT4lIHZpKCkNCmBgYA0KDQpUaGUgdmFyaWFibGUgaW1wb3J0YW5jZSBpbmRpY2F0ZXMgdGhhdCB0aGUgYWNjb21tb2RhdGVzLCBiZWRyb29tcyBhbmQgcm9vbV90eXBlIGFyZSB0aGUgbW9zdCBpbXBvcnRhbnQgdmFyaWFibGVzIGZvciBwcmVkaWN0aW5nIHRoZSBwcmljZS4gVGhlIHZhcmlhYmxlcyB3aGljaCBhcmUgdGhlIGxlYXN0IGltcG9ydGFudCBmb3IgcHJlZGljdGluZyB0aGUgcHJpY2UgYXJlIGJlZF90eXBlLCBwb29sLCBhbmQgd2lmaS4gUG9vbCBhbmQgd2lmaSBhY3R1YWxseSBoYXZlIGEgbmVnYXRpdmUgaW1wb3J0YW5jZSwgYnV0IGFzIHRoaXMgaXMgY2xvc2UgdG8gYSB2YWx1ZSBvZiAwLCBpdCBpcyBjaG9zZW4gdG8gc3RpbGwgaW5jbHVkZSB0aG9zZSB2YXJpYWJsZXMuDQoNCmBgYHtyfQ0KIyBQbG90IHZhcmlhYmxlIGltcG9ydGFuY2UNCnZhcl9pbXBvcnRhbmNlX3Bsb3QgPC0NCiAgcmZfdmlfZml0ICU+JQ0KICBwdWxsX3dvcmtmbG93X2ZpdCgpICU+JSB2aXAoZ2VvbSA9ICJwb2ludCIsIG51bV9mZWF0dXJlcyA9IDEyKSArDQogIGxhYnModGl0bGUgPSAiUmFuZG9tIEZvcmVzdCBWYXJpYWJsZSBJbXBvcnRhbmNlIikgKw0KICB0aGVtZShwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkgDQpyZl92aV9maXQNCg0KIyBTYXZlIHBsb3QgZm9yIHByZXNlbnRhdGlvbg0KZ2dzYXZlKCJwbG90cy9yZl92YXJfaW1wb3J0YW5jZS5wbmciLCBwbG90ID0gdmFyX2ltcG9ydGFuY2VfcGxvdCwNCiAgICAgICBoZWlnaHQgPSA3ICwgd2lkdGggPSAxMCkNCg0KYGBgDQoNCiMgSy1OZWFyZXN0LU5laWdoYm9ycw0KDQojIyBTZXQgdXAgdHVybmluZyBncmlkDQpgYGB7cn0NCiMgR2VuZXJhdGUgdHVuaW5nIGdyaWQgZm9yIGtubg0Ka25uX3R1bmVfZ3JpZCA8LSB0aWJibGUobmVpZ2hib3JzID0gMTo1MCoyLTEpDQpgYGANCg0KIyMgU3BlY2lmeSBhIHdvcmtmbG93IA0KDQpTb21ldGhpbmcgdGhhdCBzaG91bGQgYmUgbm90ZWQgZm9yIHRoaXMgcmVjaXBlIGlzIHRoYXQgb25seSBudW1lcmljIHZhcmlhYmxlcyBhcmUgaW5jbHVkZWQuIFRoaXMgaXMgZG9uZSBmb3IgdGhlIHJlYXNvbiB0aGF0IGNhdGVnb3JpY2FsIHZhcmlhYmxlcyB0cmFuc2xhdGUgd2l0aCBkaWZmaWN1bHR5IHRvIGEgay1uZWFyZXN0IG5laWdoYm9yIGFsZ29yaXRobS4gVGhlIHByZW1pc2Ugb2YgcHJlZGljdGlvbiBiYXNlZCBvbiBhIEtOTi1tb2RlbCBpcyB0aGF0IGl0IHJlbGllcyBleGNsdXNpdmVseSBvbiB0aGUgZGlzdGFuY2UgYmV0d2VlbiBwb2ludHMgaW4gdGhlIGRhdGEuIFRoaXMgZGlzdGFuY2UgaXMgb2J2aW91cyB3aGVuIGhhbmRsaW5nIG51bWVyaWMgdmFyaWFibGVzLiBIb3dldmVyLCB3aGVuIGRlYWxpbmcgd2l0aCBub24tbnVtZXJpYyB2YWx1ZXMgYW5kIHZhcmlhYmxlcyB0aGlzIGRpc3RhbmNlIGJldHdlZW4gZGF0YSBwb2ludHMgY2Fubm90IGVhc2lseSBiZSBtb2RlbGVkLCBwcm92aWRlZCB0aGV5IHNob3VsZCBiZSBtb2RlbGVkIGF0IGFsbC4gKFRoaXMgd2lsbCBoYXZlIGltcGxpY2F0aW9ucyBmb3IgZGV0ZXJtaW5pbmcgcHJlZGljdGlvbnMgZm9yIGltcG9ydGFuY2UgYW5kIGNvZWZmaWNpZW50cyBmb3IgdmFyaWFibGVzLCB3aGljaCB3aWxsIGJlIGFkZHJlc3NlZCBhdCB0aGUgZW5kIG9mIHRoZSBzZWN0aW9uIG9uIHRoZSBLTk4tbW9kZWwpLg0KYGBge3J9DQojIFNwZWNpZnkgbW9kZWwgDQprbm5fbW9kIDwtIA0KICBuZWFyZXN0X25laWdoYm9yKG5laWdoYm9ycyA9IHR1bmUoKSkgJT4lIA0KICBzZXRfbW9kZSgicmVncmVzc2lvbiIpICU+JSANCiAgc2V0X2VuZ2luZSgia2tubiIsIHNjYWxlPUZBTFNFKQ0Ka25uX21vZA0KDQojIFNwZWNpZnkgcmVjaXBlDQprbm5fcmVjaXBlIDwtIA0KICByZWNpcGUocHJpY2UgfiAuLCBkYXRhID0gZGF0YV90cmFpbikgJT4lIA0KICBzdGVwX3JtKGFsbF9ub21pbmFsKCkpICU+JQ0KICB1cGRhdGVfcm9sZShpZCwgbmV3X3JvbGUgPSAiaWQgdmFyIikgJT4lIA0KICBzdGVwX25vcm1hbGl6ZShhbGxfcHJlZGljdG9ycygpLCAtaWQpDQprbm5fcmVjaXBlDQpgYGANCg0KVGhlIG5vcm1hbGl6YXRpb24gb2YgdGhlIGRhdGEgaXMgZW5zdXJlZCB0aHJvdWdoIHRoZSBmb2xsb3dpbmcgY29tbWFuZHM6DQpgYGB7cn0NCiMgQ2hlY2sgbm9ybWFsaXphdGlvbiANCnRyYWluX2Jha2VkIDwtIGtubl9yZWNpcGUgJT4lIHByZXAoZGF0YV90cmFpbikgJT4lIGJha2UoZGF0YV90cmFpbikNCnRyYWluX2Jha2VkICU+JSBoZWFkKCkNCnJvdW5kKGNvbE1lYW5zKHRyYWluX2Jha2VkLCA4KSkNCnJvdW5kKGFwcGx5KHRyYWluX2Jha2VkLCAyLCBzZCksIDgpDQpybSh0cmFpbl9iYWtlZCkNCmBgYA0KDQpCZWxvdyB0aGUgaW5pdGlhbCB3b3JrZmxvdyBmb3IgdGhlIGstbmVhcmVzdCBuZWlnaGJvcnMgbW9kZWwgaXMgc3BlY2lmaWVkDQpgYGB7cn0NCiMgU3BlY2lmeSB3b3JrZmxvdw0Ka25uX3dvcmtmbG93IDwtIA0KICB3b3JrZmxvdygpICU+JSANCiAgYWRkX21vZGVsKGtubl9tb2QpICU+JSANCiAgYWRkX3JlY2lwZShrbm5fcmVjaXBlKQ0Ka25uX3dvcmtmbG93DQpgYGANCg0KIyMgVHVuaW5nIHRoZSBudW1iZXIgb2YgbmVhcmVzdCBuZWlnaGJvdXJzDQoNClRoZSBjb2RlIGJlbG93IHNlcnZlcyB0byBzcGVjaWZ5IHRoZSBhc3Nlc3NtZW50IG1ldHJpY3MgdGhhdCBhcmUgdXNlZC4gTW9yZW92ZXIsIGEgZ3JpZCBzZWFyY2ggaXMgcGVyZm9ybWVkIHVzaW5nIHRoZSB2YWxpZGF0aW9uIHNldHMuIA0KYGBge3IgbWVzc2FnZSA9IEZBTFNFfQ0KIyBTdG9yZSBtZXRyaWNzIGluIHZhcmlhYmxlDQptZXRyaWNzX3JlZyA8LSBtZXRyaWNfc2V0KHJtc2UsIG1hZSwgcnNxX3RyYWQpDQoNCiMgUGVyZm9ybSBncmlkIHNlYXJjaCB1c2luZyB2YWxpZGF0aW9uIHNldHMNCmtubl90dW5lX3JlcyA8LSANCiAga25uX3dvcmtmbG93ICU+JSANCiAgdHVuZV9ncmlkKHJlc2FtcGxlcyA9IGRhdGFfZm9sZHMsDQogICAgICAgICAgICBncmlkID0ga25uX3R1bmVfZ3JpZCwgDQogICAgICAgICAgICBtZXRyaWNzID0gbWV0cmljc19yZWcpIA0KDQojIFBsb3QgcmVzdWx0cyBtZXRyaWNzDQprbm5fbWV0cmljc19wbG90IDwtIA0KICBrbm5fdHVuZV9yZXMgJT4lICBjb2xsZWN0X21ldHJpY3MoKSAlPiUgDQogIGdncGxvdChhZXMoeCA9IG5laWdoYm9ycywgeSA9IG1lYW4pKSArDQogIGdlb21fcG9pbnQoY29sb3VyID0gInJlZCIpICsgZ2VvbV9saW5lKGNvbG91ciA9ICJyZWQiKSArDQogIGZhY2V0X3dyYXAofiAubWV0cmljLCBzY2FsZSA9ICJmcmVlX3kiKSArDQogIGxhYnModGl0bGUgPSAiS05OIFBlcmZvcm1hbmNlIE1ldHJpY3MiKSArDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKSANCmtubl9tZXRyaWNzX3Bsb3QNCg0KYXV0b3Bsb3Qoa25uX3R1bmVfcmVzKQ0KYGBgDQoNClRoZSBwbG90IG91dHB1dCBzaG93cyBzb21lIG1ldHJpY3MgdGhhdCBwbG90IHRoZSBtZWFuIG9mIHRoZSBwZXJmb3JtYW5jZSBtZXRyaWNzLiBXZSBzaG91bGQgYWltIGZvciB0aGUgTUFFIChtZWFuIGFic29sdXRlIGVycm9yKSBhbmQgUk1TRSAocm9vdCBtZWFuIHNxdWFyZSBlcnJvcikgdG8gYmUgYXMgbG93IGFzIHBvc3NpYmxlLCBhbmQgdGhlIHJzcV90cmFkIChSLXNxdWFyZWQpIHRvIGJlIGFzIGhpZ2ggYXMgcG9zc2libGUuIFdlIHVzZWQgdGhlIE1BRSBtZXRyaWMgdG8gZGV0ZXJtaW5lIHRoZSBvcHRpbWFsIGstbmVpZ2hib3JzIGZvciBvdXIgbW9kZWwsIHdoaWNoIGFycml2ZWQgYXQgNTEgbmVpZ2hib3JzLiBUaGlzIGNhbiBiZSByZWFkIGZyb20gdGhlIE1BRSBncmFwaCwgYnkgbG9va2luZyBhdCB0aGUgY29ycmVzcG9uc2luZyBrLW5laWdoYm9ycyBmb3IgdGhlIGxvd2VzdCBtZWFuIG9mIE1BRS4gDQoNCk1vcmVvdmVyLCBmcm9tIHRoZSBsYXN0IHBsb3QgdGhlIGVsYm93IHRyZW5kIGNhbiBzb21ld2hhdCBjbGVhcmx5IGJlIHNlZW46IHRoZSBtZXRyaWNzIHJlYWNoIHRoZWlyIG9wdGltdW0gcG9pbnQgYWZ0ZXIgd2hpY2ggdGhlIGxldmVsIG9mZiBhbmQgc2xvd2x5IGluY3JlYXNlIGZvciBNQUUgYW5kIFJNU0UgYW5kIGRlY3JlYXNlIGZvciBycXNfdHJhZC4NCg0KVGhlIG1vZGVsIHdpdGggdGhlIG9wdGltYWwgbnVtYmVyIG9mIGstbmVhcmVzdCBuZWlnaGJvcnMgY2FuIHRoZW4gYmUgc2VsZWN0ZWQgYXMgZm9sbG93czoNCmBgYHtyfQ0KIyBHZW5lcmF0ZSBiZXN0IG1vZGVsDQprbm5fYmVzdF9tb2RlbCA8LSBzZWxlY3RfYmVzdChrbm5fdHVuZV9yZXMsIG1ldHJpYyA9ICJtYWUiKQ0KYGBgDQoNCiMjIEZpbmFsaXplIHdvcmtmbG93DQoNCkJlbG93IHRoZSBmaW5hbGl6ZWQgd29ya2Zsb3cgaXMgbWFkZSwgd2hpY2ggYXV0b21hdGljYWxseSBwaWNrcyB0aGUgYmVzdCBLTk4tbW9kZWwgZGVmaW5lZCBhYm92ZSAod2hpY2ggaXMgc3BlY2lmaWVkIGJ5IHRoZSBNQUUgbWV0cmljKQ0KYGBge3J9DQojIEZpbmFsaXplIHdvcmtmbG93DQprbm5fd29ya2Zsb3dfZmluYWwgPC0gDQogIGtubl93b3JrZmxvdyAlPiUgDQogIGZpbmFsaXplX3dvcmtmbG93KGtubl9iZXN0X21vZGVsKQ0Ka25uX3dvcmtmbG93X2ZpbmFsDQpgYGANCg0KIyMgTGFzdCBmaXQgDQoNCkEgZmluYWwgd29ya2Zsb3cgY2FuIGJlIHNldCB1cCB0byBjaGVjayB0aGUgZmluYWwgZml0LiBGdXJ0aGVybW9yZSwgdGhlIHBlcmZvcm1hbmNlIG1ldHJpY3MgZm9yIHRoZSBiZXN0IEtOTi1tb2RlbCBhcmUgc2VsZWN0ZWQgYW5kIHB1dCBpbiBhIHRhYmxlLg0KYGBge3J9DQojIFRyYWluIGFuZCB0ZXN0IHRoZSBkYXRhIHNldA0Ka25uX2xhc3RfZml0IDwtIA0KICBrbm5fd29ya2Zsb3dfZmluYWwgJT4lIA0KICBsYXN0X2ZpdChkYXRhX3NwbGl0LCANCiAgICAgICAgICAgbWV0cmljcyA9IG1ldHJpY3NfcmVnKQ0KYGBgDQoNCiMjIEtOTiB2YXJpYWJsZSBpbXBvcnRhbmNlIA0KDQpLTk4sIGFzIGEgbWV0aG9kLCBkb2VzIG5vdCBjb21lIHdpdGggYSBwcmVkaWN0aW9uIGZvciB0aGUgaW1wb3J0YW5jZSBvciBjb2VmZmljaWVudHMgb2YgdmFyaWFibGVzLiBUaGUgcmVhc29uIGZvciB0aGlzIGhhcyB0byBkbyB3aXRoIHRoZSBmYWN0IHRoYXQgcHJlZGljdGlvbiBpbiBhIGstbmVhcmVzdCBuZWlnaGJvciBtb2RlbCByZWxpZXMgZXhjbHVzaXZlbHkgb24gdGhlIGRpc3RhbmNlIGJldHdlZW4gZGF0YSBwb2ludHMuIFdpdGggdGhpcyBjb21lcyB0aGUgYWRkZWQgaW1wbGljYXRpb24gdGhhdCBubyBpbmZvcm1hdGlvbiBhYm91dCB0aGUgcmVsYXRpdmUgaW1wb3J0YW5jZSBvZiB2YXJpYWJsZXMgY2FuIGJlIGRlcml2ZWQgZnJvbSBpdC4NCg0KDQojIFBhcnQgMzogTW9kZWwgQ29tcGFyaXNvbg0KDQpJbiBvcmRlciB0byBhc3Nlc3MgdGhlIHBlcmZvcm1hbmNlIG9mIHRoZSB0aHJlZSBtb2RlbHMgdGhlIHJlc3VsdHMgb2YgdGhyZWUgbWV0cmljcyBhcmUgY29tcGFyZWQuIA0KDQoxLiBSb290IG1lYW4gc3F1YXJlZCBlcnJvci4gVGhlIG9iamVjdGl2ZSBpcyB0byBtaW5pbWl6ZSB0aGUgcmVzdWx0IG9mIHRoaXMgbWV0cmljLiBBbiBpbXBsaWNhdGlvbiBpcyB0aGF0IHRoZSBtZXRyaWMgaXMgdmVyeSBzZW5zaXRpdmUgdG8gb2JzZXJ2YXRpb25zIHdpdGggbGFyZ2UgYWJzb2x1dGUgcmVzaWR1YWxzLiANCjIuIE1lYW4gYWJzb2x1dGUgZXJyb3IuIFRoZSBvYmplY3RpdmUgaXMgdG8gbWluaW1pemUgdGhlIHJlc3VsdCBvZiB0aGlzIG1ldHJpYy4gVGhpcyBtZXRyaWMgaXMgbW9yZSByb2J1c3QgYW5kIHRoZXJlZm9yZSBsZXNzIHNlbnNpdGl2ZSB0byBvYnNlcnZhdGlvbnMgd2l0aCBsYXJnZSBhYnNvbHV0ZSByZXNpZHVhbHMuIEhvd2V2ZXIsIGJlY2F1c2UgaXQgdXNlcyB0aGUgbWVhbiwgaXQgaXMgdGhlcmVmb3JlIG5vdCBpbnNlbnNpdGl2ZSB0byBza2V3ZWQgZGlzdHJpYnV0aW9ucy4gDQozLiBSLXNxdWFyZWQuIEFuIGF0dHJhY3Rpb24gaXMgdGhhdCB0aGUgbWV0cmljIGlzIHVuaXRsZXNzIGFuZCBjYW4gdGhlcmVmb3JlIGJlIGNvbXBhcmVkIGFjcm9zcyBtb2RlbHMuIEEgZG93bnNpZGUgaXMgdGhhdCBpcyBub3Qgcm9idXN0LCBzaW5jZSBpdCBlc3NlbnRpYWxseSBtZWFzdXJlcyBjb3JyZWxhdGlvbiBhbmQgbm90IGFncmVlbWVudC4gDQoNCiMjIEFzc2VzcyBhcHByb3ByaWF0ZW5lc3MgbWV0cmljcyANCg0KSW4gb3JkZXIgdG8gY2hlY2sgaWYgdGhlIG1ldHJpY3MgYXJlIGFuIGFwcHJvcHJpYXRlIGZpdCwgdGhlIHJlc2lkdWFscyBkaXN0cmlidXRpb25zIG9mIHRoZSBtb2RlbHMgYXJlIHBsb3R0ZWQuIFNpbmNlIHRoZSBwbG90cyBiZWxvdyBzaG93IG5vIGxhcmdlIG91dGxpZXJzIGFuZCBubyBza2V3ZWQgZGlzdHJpYnV0aW9ucywgdGhlcmUgYXJlIG5vIGltcGxpY2F0aW9ucyBmb3Igcm9vdCBtZWFuIHNxdWFyZWQgZXJyb3IgYW5kIG1lYW4gYWJzb2x1dGUgZXJyb3IuIA0KYGBge3IgZWNobyA9IFRSVUV9DQojIEdlbmVyYXRlIHByZWRpY3RlZCB2YWx1ZXMgZm9yIHNhbGVzDQpsYXNzb190ZXN0X3ByZWRzIDwtIA0KICBsYXNzb193Zl90dW5lZCAlPiUgDQogIGZpdChkYXRhID0gZGF0YV90cmFpbikgJT4lDQogIHByZWRpY3QoZGF0YV90ZXN0KSAlPiUgDQogIHB1bGwoLnByZWQpDQoNCiMgQ3JlYXRlIHRpYmJsZSBmb3IgZGlzdHJpYnV0aW9uIHBsb3QNCmxhc3NvX3ByZWQgPC0gDQogIHRpYmJsZShvYnNlcnZlZCA9IGRhdGFfdGVzdCRwcmljZSwgDQogICAgICAgICBwcmVkaWN0ZWQgPSBsYXNzb190ZXN0X3ByZWRzLCANCiAgICAgICAgIHJlc2lkdWFsID0gb2JzZXJ2ZWQgLSBwcmVkaWN0ZWQpDQoNCiMgUGxvdCBkaXN0cmlidXRpb24gcmVzaWR1YWxzDQpsYXNzb19yZXNpZHVhbF9wbG90IDwtIA0KICBsYXNzb19wcmVkICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gcmVzaWR1YWwpKSArDQogIGdlb21fZGVuc2l0eShidyA9IDAuMTUsIGZpbGwgPSAic3ByaW5nZ3JlZW4iLCBhbHBoYSA9IDAuNSkgKw0KICBnZW9tX3J1ZygpICsNCiAgbGFicyh0aXRsZSA9ICJMYXNzbyBSZWd1bGFyaXplZCBSZWdyZXNzaW9uIERpc3RyaWJ1dGlvbiBSZXNpZHVhbHMiKSArDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKSArDQogIGNvb3JkX2NhcnRlc2lhbih5bGltID0gYygwLCAxLjUpKQ0KbGFzc29fcmVzaWR1YWxfcGxvdA0KYGBgDQoNCmBgYHtyfQ0KIyBHZW5lcmF0ZSBwcmVkaWN0ZWQgdmFsdWVzIGZvciBzYWxlcw0Kc2V0LnNlZWQoMTIzNDUpDQpyZl90ZXN0X3ByZWRzIDwtIA0KICByZl92aV93ZiAlPiUgDQogIGZpdChkYXRhID0gZGF0YV90cmFpbikgJT4lDQogIHByZWRpY3QoZGF0YV90ZXN0KSAlPiUgDQogIHB1bGwoLnByZWQpDQoNCiMgQ3JlYXRlIHRpYmJsZSBmb3IgZGlzdHJpYnV0aW9uIHBsb3QNCnJmX3ByZWQgPC0gDQogIHRpYmJsZShvYnNlcnZlZCA9IGRhdGFfdGVzdCRwcmljZSwgDQogICAgICAgICBwcmVkaWN0ZWQgPSByZl90ZXN0X3ByZWRzLCANCiAgICAgICAgIHJlc2lkdWFsID0gb2JzZXJ2ZWQgLSBwcmVkaWN0ZWQpDQoNCiMgUGxvdCBkaXN0cmlidXRpb24gcmVzaWR1YWxzDQpyZl9yZXNpZHVhbF9wbG90IDwtIA0KICByZl9wcmVkICU+JSANCiAgZ2dwbG90KGFlcyh4ID0gcmVzaWR1YWwpKSArDQogIGdlb21fZGVuc2l0eShidyA9IDAuMTUsIGZpbGwgPSAic3ByaW5nZ3JlZW4iLCBhbHBoYSA9IDAuNSkgKw0KICBnZW9tX3J1ZygpICsNCiAgbGFicyh0aXRsZSA9ICJSYW5kb20gRm9yZXN0IERpc3RyaWJ1dGlvbiBSZXNpZHVhbHMiKSArDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKSArDQogIGNvb3JkX2NhcnRlc2lhbih5bGltID0gYygwLCAxLjUpKQ0KcmZfcmVzaWR1YWxfcGxvdA0KYGBgDQoNCmBgYHtyfQ0KIyBHZW5lcmF0ZSBwcmVkaWN0ZWQgdmFsdWVzIGZvciBwcmljZQ0Ka25uX3Rlc3RfcHJlZHMgPC0gDQogIGtubl93b3JrZmxvd19maW5hbCAlPiUgDQogIGZpdChkYXRhID0gZGF0YV90cmFpbikgJT4lDQogIHByZWRpY3QoZGF0YV90ZXN0KSAlPiUgDQogIHB1bGwoLnByZWQpDQoNCiMgQ3JlYXRlIHRpYmJsZSBmb3IgZGlzdHJpYnV0aW9uIHBsb3QNCmtubl9wcmVkIDwtIA0KICB0aWJibGUob2JzZXJ2ZWQgPSBkYXRhX3Rlc3QkcHJpY2UsIA0KICAgICAgICAgcHJlZGljdGVkID0ga25uX3Rlc3RfcHJlZHMsIA0KICAgICAgICAgcmVzaWR1YWwgPSBvYnNlcnZlZCAtIHByZWRpY3RlZCkNCg0KIyBQbG90IGRpc3RyaWJ1dGlvbiByZXNpZHVhbHMNCmtubl9yZXNpZHVhbF9wbG90IDwtIA0KICBrbm5fcHJlZCAlPiUgDQogIGdncGxvdChhZXMoeCA9IHJlc2lkdWFsKSkgKw0KICBnZW9tX2RlbnNpdHkoYncgPSAwLjE1LCBmaWxsID0gInNwcmluZ2dyZWVuIiwgYWxwaGEgPSAwLjUpICsNCiAgZ2VvbV9ydWcoKSArDQogIGxhYnModGl0bGUgPSAiS05OIERpc3RyaWJ1dGlvbiBSZXNpZHVhbHMiKSArDQogIHRoZW1lKHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKSArDQogIGNvb3JkX2NhcnRlc2lhbih5bGltID0gYygwLCAxLjUpKQ0Ka25uX3Jlc2lkdWFsX3Bsb3QNCg0KYGBgDQoNCiMjIEFzc2Vzc21lbnQgbWV0cmljcw0KDQpUaGUgdGFibGUgYmVsb3cgc2hvd3MgcmVzdWx0cyBmb3IgdGhlIG1ldHJpY3MgZm9yIHRoZSB0aHJlZSBtb2RlbHMuIFdoZW4gYXNzZXNzaW5nIHRoZSBtZXRyaWNzIGFuZCB0aGVpciBvYmplY3RpdmVzLCB0aGUgcmVzdWx0cyBzaG93IHRoYXQgdGhlIHJhbmRvbSBmb3Jlc3QgbW9kZWwgcGVyZm9ybXMgYmVzdCBvbiBhbGwgbWV0cmljcy4gVGhlcmVmb3JlLCB0aGUgcmFuZG9tIGZvcmVzdCBpcyBjb25zaWRlcmVkIHRvIGJlIHRoZSBiZXN0IG1vZGVsLiANCmBgYHtyfQ0KIyBHZW5lcmF0ZSB0YWJsZSB3aXRoIA0KbGFzc29fbWV0cmljc19jb21wYXJlIDwtIA0KICBsYXNzb190ZXN0X21ldHJpY3MgJT4lIA0KICBzZWxlY3QoLS5lc3RpbWF0b3IpICU+JSANCiAgbXV0YXRlKG1vZGVsID0gImxhc3NvIHJlZ3Jlc3Npb24iKQ0KcmZfbWV0cmljc19jb21wYXJlIDwtIA0KICBmaW5hbF9yZXMgJT4lDQogIGNvbGxlY3RfbWV0cmljcygpICU+JSANCiAgbXV0YXRlKG1vZGVsID0gInJhbmRvbSBmb3Jlc3QiKQ0Ka25uX21ldHJpY3NfY29tcGFyZSA8LSANCiAga25uX2xhc3RfZml0ICU+JSANCiAgY29sbGVjdF9tZXRyaWNzICU+JSANCiAgc2VsZWN0KC0uZXN0aW1hdG9yKSAlPiUgDQogIG11dGF0ZShtb2RlbCA9ICJrbm4gcmVnIikNCmxhc3NvX21ldHJpY3NfY29tcGFyZSAlPiUNCiAgYmluZF9yb3dzKHJmX21ldHJpY3NfY29tcGFyZSwga25uX21ldHJpY3NfY29tcGFyZSkgJT4lIA0KICBzZWxlY3QoLS5lc3RpbWF0b3IpICU+JSANCiAgcGl2b3Rfd2lkZXIobmFtZXNfZnJvbSA9IC5tZXRyaWMsIHZhbHVlc19mcm9tID0gLmVzdGltYXRlKQ0KYGBgDQoNCiMgUGFydCA0OiBSZWNvbW1lbmRhdGlvbnMNCg0KRm9yIHRoaXMgYXNzaWdubWVudCB3ZSBhc3Nlc3NlZCB0aHJlZSBtb2RlbHMgZm9yIHByZWRpY3RpbmcgcHJpY2VzIG9uIHRoZSBBaXJibmIgcGxhdGZvcm0uIFRoZXNlIHRocmVlIG1vZGVscyBhcmUgYSBsYXNzbyByZWd1bGFyaXplZCBsaW5lYXIgcmVncmVzc2lvbiwgYSByYW5kb20gZm9yZXN0IGFuZCBmaW5hbGx5IGEgSy1OZWFyZXN0IE5laWdoYm91cnMgbW9kZWwuIFRoZSBtb2RlbHMgYXJlIGFzc2Vzc2VkIG9uIHRocmVlIGRpZmZlcmVudCBtZXRyaWNzLCBuYW1lbHkgdGhlIHJvb3QgbWVhbiBzcXVhcmVkIGVycm9yIChSTVNFKSwgdGhlIG1lYW4gc3F1YXJlZCBlcnJvciAoTUFFKSBhbmQgdGhlIHItc3F1YXJlZC4gVGhlIHByb3Bvc2VkIGFzc2Vzc21lbnQgbWV0cmljcyBpbmRpY2F0ZSB0aGF0IHRoZSByYW5kb20gZm9yZXN0IG91dHBlcmZvcm1zIHRoZSBsYXNzbyByZWd1bGFyaXplZCBsaW5lYXIgcmVncmVzc2lvbiBhbmQgdGhlIEstTmVhcmVzdC1OZWlnaGJvciBpbiBhbGwgcHJvcG9zZWQgbWV0cmljcy4NCg0KRnVydGhlcm1vcmUsIHRoZSB2YXJpYWJsZSBpbXBvcnRhbmNlIG9mIHRoZSByYW5kb20gZm9yZXN0IGluZGljYXRlcyB3aGljaCB2YXJpYWJsZXMgbGVhZCB0byB0aGUgaGlnaGVzdCBpbmNyZWFzZSBpbiBSLXNxdWFyZWQuIEFjY29tbW9kYXRlcywgYmVkcm9vbXMgYW5kIHJvb21fdHlwZSBhcmUgdGhlIG1vc3QgaW1wb3J0YW50IHZhcmlhYmxlcyBmb3IgcHJlZGljdGluZyB0aGUgcHJpY2UuIEJlZF90eXBlLCBwb29sLCBhbmQgd2lmaSBhcmUgdGhlIGxlYXN0IGltcG9ydGFudCBmb3IgcHJlZGljdGluZyB0aGUgcHJpY2UuIFdlIHRoZXJlZm9yZSBhZHZpc2UgaG9zdHMgdG8gc3BlY2lmaWNhbGx5IGxvb2sgYXQgdGhlIHZhcmlhYmxlcyB3aXRoIGEgaGlnaCBpbXBvcnRhbmNlLCBhcyB0aGVzZSB2YXJpYWJsZXMgaGF2ZSB0aGUgaGlnaGVzdCBpbXBhY3Qgb24gdGhlaXIgcHJlZGljdGVkIHByaWNlLg0KDQpBcyB0aGUgbW9kZWwgcGVyZm9ybWFuY2UgbWV0cmljcyB3ZXJlIHVzZWQgdG8gY29tcGFyZSB0aGUgbW9kZWxzIGFuZCB0byBzZWxlY3QgdGhlIGJlc3Qgb25lLCB0aGVzZSBtZXRyaWNzIHNob3VsZCBub3QgYmUgdXNlZCB0byBlc3RpbWF0ZSB0aGUgZ2VuZXJhbGl6YXRpb24gZXJyb3IsIG9yIGhvdyB3ZWxsIHRoZSBtb2RlbCB3b3VsZCBwZXJmb3JtIG9uIGNvbXBsZXRlbHkgbmV3IGRhdGEuIEZvciB0aGlzIHB1cnBvc2UsIGl0IGlzIHJlY29tbWVuZGVkIHRoYXQgdGhlIHJhbmRvbSBmb3Jlc3QgbW9kZWwgd2lsbCBiZSBmdXJ0aGVyIHRlc3RlZCBpbiBhbiBvbmxpbmUgZW52aXJvbm1lbnQgYmVmb3JlIHNjYWxpbmcgdXAgaXRzIGltcGxlbWVudGF0aW9uLiBBZGRpdGlvbmFsbHksIGluIHByYWN0aWNlLCB0aGUgbW9kZWwgd2lsbCBwcm92aWRlIHRoZSBwcmVkaWN0aW9uIGluIGxvZyBwcmljZXMsIGFuZCB0aGlzIGhhcyB0byBiZSBjb252ZXJ0ZWQgdG8gZXVyb3MuIEZvciBleGFtcGxlLCBhIGxvZyBwcmljZSBwcmVkaWN0aW9uIG9mIDQuMDkgd291bGQgcmVmbGVjdCBwcmljZSBvZiDigqw1OS43NC4NCg0KSG93IGFyZSB0aGVzZSBmaW5kaW5ncyBvZiB1c2UgdG8gQWlyYm5iPyBFc3NlbnRpYWxseSwgdGhpcyBwcm9qZWN0IGhhcyBzb3VnaHQgdG8gZXhhbWluZSB0aHJlZSBhcHByb2FjaGVzIHRvIGNvbXBldGl0aXZlbHkgc2V0IGxpc3RpbmcgcHJpY2VzIG9mIEFpcmJuYiBsaXN0aW5ncy4gQ29uc2lkZXJpbmcgb3VyIHJlc3VsdHMsIHdlIGFkdmlzZSBBaXJibmIgdG8gdXNlIGEgcmFuZG9tIGZvcmVzdCBtb2RlbCBpbiB0aGVpciBwcm9qZWN0cyB0aGF0IGRlYWwgd2l0aCBvcHRpbWFsIHByaWNpbmcgb2YgbGlzdGluZ3MuICANCg0KDQo=